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:

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

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

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.

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

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

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.