Perl-Sensitive Sunglasses PerlMonks

### •Re: Puzzle: need a more general algorithm

by merlyn (Sage)
 on Jul 08, 2002 at 20:35 UTC ( #180316=note: print w/replies, xml ) Need Help??

in reply to Puzzle: need a more general algorithm

One other thing to notice is that a particular distribution can be identified by a binary string of length equal to one less than the number of categories, and a number of 1-bits equal to one less than the number of columns. Each 0-bit denotes that the next category is in the same column as the prior category, while a 1-bit denotes that the next category begins the next column over. Since the first category is forced into the first column, and the last category is forced into the last column, we get two freebies there.

So the total number of distributions of N categories into M columns is equal to the number of combinations of N-1 things taken M-1 at a time.

Dunno if this helps, but it should keep you from brute forcing more than you need. {grin}

In fact, for your particular dataset (6 categories, 4 columns), you shouldn't need to brute force more than (5 items taken 3 at a time which is) 10 tries.

Wow, that's less than I thought! But it desk checks properly. All you need is a good generating algorithm, and you can brute force this!

• Comment on •Re: Puzzle: need a more general algorithm

Replies are listed 'Best First'.
Re: •Re: Puzzle: need a more general algorithm
by Ovid (Cardinal) on Jul 09, 2002 at 05:03 UTC

merlyn wrote: All you need is a good generating algorithm and you can brute force this!

I thought this idea was so intensely cool that I just had to try it out. However, coming up with a "good generating alorithm" escapes me. First, I took the list of possible permutations that dws created and translated it:

```
[1][2][3][4,5,6]
1  1  1  0 0
[1][2][3,4][5,6]
1  1  0 1  0
[1][2][3,4,5][6]
1  1  0 0 1
[1][2,3][4][5,6]
1  0 1  1  0
[1][2,3][4,5][6]
1  0 1  0 1
[1][2,3,4][5][6]
1  0 0 1  1
[1,2][3][4][5,6]
0 1  1  1  0
[1,2][3][4,5][6]
0 1  1  0 1
[1,2][3,4][5][6]
0 1  0 1  1
[1,2,3][4][5][6]
0 0 1  1  1

Then, once I was sure I understood it, I went ahead and hardcoded that so I could manipulate it and look for patterns.

```#!/usr/bin/perl -w
use strict;
use Data::Dumper;

my @categories = qw/
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111
/;

@categories = sort @categories;
my @cat2 =
sort { \$a <=> \$b }
map  { ord pack 'b*', \$_ }
@categories;

print Dumper \@categories, \@cat2;

Which prints the following:

```\$VAR1 = [
'00111',
'01011',
'01101',
'01110',
'10011',
'10101',
'10110',
'11001',
'11010',
'11100'
];
\$VAR2 = [
7,
11,
13,
14,
19,
21,
22,
25,
26,
28
];

Needless to say, the list seems arbitrary (even though we know it's not) and try as I might, I can't come up with a method of creating that, much less writing a generalized routine. I thought about trying to discover a pattern in the sequences, but no dice. Later, I tried creating a "picture" of the bits and swapping pairs, but I couldn't come up with a sequence for that, either. I'll start looking into permutators, but I feel like I'm missing something awfully basic here. There are only 10 possible combinations, so I didn't think generating them would be that hard :(

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

```          '00111',
'01011',
'01101',
'01110',
'10011',
'10101',
'10110',
'11001',
'11010',
'11100'

So it looks like you're shifting the highest bit up by one, then the next highest bit, then the next, until you've run out of empty bits. How about something like (untested):

```  use Bit::Vector;

my \$joins  = 2;
my \$splits = 3;
my \$length = \$joins+\$splits;
my \$start  = '0'x\$joins . '1'x\$splits;

my \$vector = Bit::Vector->new_Bin(\$length, \$start);
my @combinations = ();

for my \$pos (\$joins-1..\$length-1) { # 0-based, right?
for my \$bit (\$splits-1..0) {
\$vector->bit_flip(\$pos+\$bit);
\$vector->bit_flip(\$pos+\$bit-1);
push @combinations, \$vector->to_Bin();
}
}

--
The hell with paco, vote for Erudil!
:wq

Tempting, but the this is the "swapping bits" that I was referring to. The solution skips these three combinations:

```   01101
01110
10110

If you look at them closely, you'll see why you can't generate them. That's what got me stuck on this track. If that can be solved, this is a good way to go.

Oh, and since you mentioned this was untested, I won't comment about for my \$bit (\$splits-1..0) { :)

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

As we discussed in that meeting, here's the code snippet I was thinking about to generate the binary strings:
```print map "\$_\n", strings_for(6, 4);

sub strings_for {
my (\$cats, \$cols) = @_;
\$cats--; \$cols--;
my @ret;
for (0..(1 << \$cats) - 1) {
my \$bitstring = substr(unpack("B*", pack "N", \$_), -\$cats);
next unless \$bitstring =~ tr/1// == \$cols;
push @ret, \$bitstring;
}
@ret;
}
Re: •Re: Puzzle: need a more general algorithm
by Anonymous Monk on Jul 08, 2002 at 21:21 UTC
Counter example:
```1 2 3 4     1 2 3 4     1 2 3 4
5     6       5   6         5 6

1 3 4 5     1 3 4 5     1 3 4 5
2     6       2   6         2 6

1 2 3 6     1 2 3 6     1 2 3 6
4 5           4 5           4 5

1 2 3 6     1 2 3 6     1 2 3 6
4   5       4     5       4   5

...

That's twelve tries and there are more still.

That's twelve tries and there are more still.

No, there are only 10. Your attempt at a counter example violates the requirement that "The categories must remain in order".

My apologies. I misread that requirement entirely.

Create A New User
Node Status?
node history
Node Type: note [id://180316]
help
Chatterbox?
and the pool shimmers...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2018-06-25 06:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (126 votes). Check out past polls.

Notices?