Re: •Re: 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
[download]

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;
[download]

Which prints the following:

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 Select or Download Code

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'` [download] 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(); } }` [download] `-- The hell with paco, vote for Erudil! :wq`	[reply] [d/l] [select]
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` [download] 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.	[reply] [d/l] [select]
Re(5): Puzzle: need a more general algorithm by FoxtrotUniform (Prior) on Jul 09, 2002 at 15:04 UTC
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`	[reply]
Re: Re (5): Puzzle: need a more general algorithm by Ovid (Cardinal) on Jul 09, 2002 at 15:42 UTC
•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; }` [download] -- Randal L. Schwartz, Perl hacker	[reply] [d/l]


Think about Loose Coupling
	PerlMonks