Shayk has asked for the wisdom of the Perl Monks concerning the following question:

Alright gurus, here's something that's been stumping me. I've got the following arrays:

my @ControlMatrix = ( [ 1, 2, 1, 0, 0, 1, 2, 1, 1, 2, 1 ], [ 1, 1, 2, 0, 0, 1, 2, 2, 1, 1, 0 ], [ 1, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0 ] ); my @ControlNames = ('Label', 'Textbox', 'Button');

@ControlMatrix describes controls on a page, with the first dimension being the control (corresponding to the entries in @ControlNames) and the second dimension being the field requirements for the control. A 1 denotes a "required" field, a 2 denotes an "optional" field, and a 0 denotes a field not included on this control.

What I'd like to do is output a 2D array of all the possible permutations of optional fields for each control.

For example, for the first control this would output:

( [ 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1 ], [ 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1 ], [ 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1 ], [ 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1 ], [ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1 ], [ 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1 ], [ 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1 ], [ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1 ] )

Anyone have an elegant way to do this?

Shayk

Replies are listed 'Best First'.
Re: Permutation algorithm?
by chromatic (Archbishop) on Oct 20, 2000 at 06:59 UTC
    If I understand this correctly, you need to walk through each element of @ControlMatrix. If you find a 2, you've hit a branch, and you'll have to copy the existing array and replace the 2 with a 1 in one and a 0 in the other.

    This isn't that hard to code, but it's a recursive solution. There are a couple of possibilities. The easiest, if you're familiar with the data structure, would be to turn the arrays into trees. Then, just follow all of the paths from root to leaves.

    The other way is similar, but you don't have to build a tree to do it. Write a function that steps through the elements of an array it's given, calls itself when it hits a 2, and returns an array of all of the possible branches. Glue everything together (the only hard part besides getting the recursion correct), and you're in business.

    I could provide demo code if you're really curious, but it's nearly naptime.

RE (tilly) 1 (not): Permutation algorithm?
by tilly (Archbishop) on Oct 20, 2000 at 13:14 UTC
    First of all this is not really a permutation algorithm. Permutations are rearrangements of things, you want instead a list of possibilities. Which is a rather different problem. Anyways here is a cheesy answer.
    use Carp; sub print_possib { my @array = @_; my $pat = 0; # Counter used as a bit-vector print "(\n"; # A merlyn loop. { my $x = $pat; my @row; foreach my $i (@array) { if (2 == $i) { # Use the bit-vector to choose what to do now push @row, $x&1 ? 1 : 0; $x >>= 1; # Shift off the used bit } elsif (0 == $i or 1 == $i) { push @row, $i; } else { confess "Illegal value $i: Legal ones are 0, 1, and 0"; } } if ($x) { # We have more bits than needed, would start repeating. # So end instead print " )\n"; return; } else { print ( ($pat ? ",\n [ " : "( [ "), # Start or divider (join ", ", @row), # Row " ]" ); # Close the row ++$pat; redo; } } } print_possib(@ARGV);
RE: Permutation algorithm?
by Petruchio (Vicar) on Oct 20, 2000 at 16:39 UTC
    I'm running out the door, but I wanted to make a tangential point before I go. Consider whether you really want to use parallel arrays... looks to me like you'd rather say:

    my %ControlMatrix; $ControlMatrix{Label} = [ 1, 2, 1, 0, 0, 1, 2, 1, 1, 2, 1 ]; $ControlMatrix{Textbox} = [ 1, 1, 2, 0, 0, 1, 2, 2, 1, 1, 0 ]; $ControlMatrix{Button} = [ 1, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0 ];

    After all, that's what hashes are for, right? :-)

Re: Permutation algorithm?
by Lexicon (Chaplain) on Oct 20, 2000 at 12:42 UTC
    Hope this helps. But: 1) I'm a CS/Math Major, but I don't speak perl (yet). 2) I only spent like 10 minuts on this. 3) I havn't even tried to compile this. Summary) Here's a nice non-recursive algorithm, but I won't vouch for the code. ;) It should take the @ControlMatrix and produce a 3 dimensional array @perms that looks something like this:
    @ControlMatrix = ( [1, 2, 0, 2], [0, 0, 2, 1] ) @perms = ( ([1, 0, 0, 0], [1, 1, 0, 0], [1, 0, 0, 1], [1, 1, 0, 1]) ([0, 0, 0, 1], [1, 1, 1, 1]) )
    Here's my guess:
    $index = 0; $pcount = 1; for ($names = 0; $names < @ControlNames.length; $names++) { for ($fields = 0; $fields < $ControlMatrix[$names].length; $fields++ +) { if (@ControlMatrix[$names][$fields] < 2 ) { for ($q = 0; $q < $pcount; $q++) { @perms[$names][$q][$fields] = @ControlMatrix[$names][$fields]; } } else { for ($q = 0; $q < $pcount; $q++) { @perms[$names][$q+$pcount] = @perms[names][$q]; $perms[$names][$q][$fields] = 0; $perms[$names][$q+$pcount][$fields] = 1; } $pcount *= 2; } } }
Why get all of the arrays?
by tedv (Pilgrim) on Oct 20, 2000 at 22:53 UTC
    The number of different arrays you'll get should equal 2^x, where x is the number of optional fields. Anything involving an exponential number of data structures should be avoided, so my strong sense is that what you're asking for is not what you need. What exactly are you using this data for?

    Incidently, you definitly want to use hashes like Petruchio explained. I also feel like the input data structures of lists of integer values are... somewhat abstract and meaningless. In languages like C where it's difficult to wrap meaning up with context, this makes sense. In perl, there is probably a better way of further organizing this data.

    To wit, can we have more context?

    -Ted