laziness, impatience, and hubris PerlMonks

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

by Ovid (Cardinal)
 on Jul 09, 2002 at 05:03 UTC ( #180413=note: print w/ replies, xml ) Need Help??

in reply to •Re: Puzzle: need a more general algorithm
in thread Puzzle: need a more general algorithm

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.

Comment on Re: •Re: Puzzle: need a more general algorithm
Replies are listed 'Best First'.
Re(3): Puzzle: need a more general algorithm
by FoxtrotUniform (Prior) on Jul 09, 2002 at 05:28 UTC
```          '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.

D'oh!

Fortunately, a man far smarter than I has written an article that you might find useful. ("Pre-Fascicle 2c: Generating all combinations", about halfway down the page. The draft is a .ps.gz file, which is why I didn't link to it directly.)

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

•Re: Re: •Re: Puzzle: need a more general algorithm
by merlyn (Sage) on Jul 12, 2002 at 19:39 UTC
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;
}

Create A New User
Node Status?
node history
Node Type: note [id://180413]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (19)
As of 2015-08-04 14:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?