http://qs1969.pair.com?node_id=180413


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.

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; }

    -- Randal L. Schwartz, Perl hacker