Your skill will accomplishwhat the force of many cannot PerlMonks

### Re(3): Puzzle: need a more general algorithm

by FoxtrotUniform (Prior)
 on Jul 09, 2002 at 05:28 UTC ( #180416=note: print w/replies, xml ) Need Help??

```          '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

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

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

After giving this some thought, I realized that traditional permutation generators are going to have a problem here. Consider the following four permutations:

```11100
11100
11100
11100

Those can be different permutations. The second could have the first and second ones swapped, the third could have the last fourth and fifth zeroes swapped, etc. Even though, to us, they look the same, the permutators that I've played with don't see that (and how would they calculate it?).

And it was an interesting coincidence to see the Knuth thread on /. this morning. I'm checking it out now.

Cheers,
Ovid

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

Create A New User
Node Status?
node history
Node Type: note [id://180416]
help
Chatterbox?
 [ovedpo15]: another question about regex. if I have a string like this: "a/b/,c/d/e,5" I would like to remove the string after the last comma so the output will be "a/b/,c/d/e" how to do so? [Corion]: ovedpo15: You could split on comma, and then join everything together, except the last part. Or you could match and make sure that the last part has no comma, like qr!,[^,]+\$!, or you could use rindex.

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2018-05-27 10:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (194 votes). Check out past polls.

Notices?