comment on

The problem

For an algorithm related to code generation I need to permute the values of an array, but in addition to a regular permutation, I need also to report the partial permutation of the values.

VALUES
a b c
1 2 3
x y z

PERMUTATIONS
a1x a1y a1z   a1
a2x a2y a2z   a2
a3x a3y a3z   a3 a
b1x b1y b1z   b1
b2x b2y b2z   b2
b3x b3y b3z   b3 b
c1x c1y c1z   c1
c2x c2y c2z   c2
c3x c3y c3z   c3 c
[download]

In the example above, the first three columns are the result of a standard permutation, in addition to that, I need to generate "a1" when it is no longer part of the permuted value. Therefore, before "a2x", I need to create "a1", before "b1x" I must create "a3". The same goes for "a", which is generated immediately before the permuted value starts showing "b".

I hope the example is clearer than my explanation. :)

Research

I found several permutation examples, and I tried out merlyn's Permutations and combinations. It works as advertised, but it doesn't do what I need.

Other variants of permutation algorithms don't offer any handle to do what I need, and some don't even guarantee a given order.

#!/usr/bin/perl -w
use strict;

my @array = (
    [ 'a', 'b', 'c' ],
    [ 1, 2 ],
    ['x', 'y', 'z'],
    [7, 8, 9]
);

sub permute {                 # merlyn's
  my $last = pop @_;
  unless (@_) {
    return map [$_], @$last;
  }
  return map { my $left = $_; map [@$left, $_], @$last } permute(@_);
}

print  join("", @$_), " " for permute(@array);
print "\n";
__END__
a1x7 a1x8 a1x9         a1y7 a1y8 a1y9         a1z7 a1z8 a1z9
a2x7 a2x8 a2x9         a2y7 a2y8 a2y9         a2z7 a2z8 a2z9
b1x7 b1x8 b1x9         b1y7 b1y8 b1y9         b1z7 b1z8 b1z9
b2x7 b2x8 b2x9         b2y7 b2y8 b2y9         b2z7 b2z8 b2z9
c1x7 c1x8 c1x9         c1y7 c1y8 c1y9         c1z7 c1z8 c1z9
c2x7 c2x8 c2x9         c2y7 c2y8 c2y9         c2z7 c2z8 c2z9
[download]

my solution

The problem is recursive, not only that, but it has also some reminiscence of tree traversal, so I tried with a Tree.

#!/usr/bin/perl -w
use strict;
use Tree::DAG_Node;

my @array = (
    [ 'a', 'b', 'c' ],
    [ 1, 2 ],
    ['x', 'y', 'z'],
    [7, 8, 9]
);

my $tree = Tree::DAG_Node->new;
$tree->name('cols');

sub add_values {
    my $top = shift;
    my $matrix = shift;
    my $level = shift;
    return if $level > $#$matrix;
    my $values = $array[$level];
    $top->new_daughter->name($_) for @$values;
    add_values($_, $matrix, $level+1) for $top->daughters;
}

add_values($tree, \@array, 0);

$tree->walk_down ({
    callbackback => sub {
        my $node = shift;
        print join ( "", reverse map {$_->name}
            grep {$_->address ne '0'}
            $node, $node->ancestors)," ";
    }
});
print "\n";

__END__
a1x7 a1x8 a1x9   a1x   a1y7 a1y8 a1y9   a1y   a1z7 a1z8 a1z9   a1z a1
a2x7 a2x8 a2x9   a2x   a2y7 a2y8 a2y9   a2y   a2z7 a2z8 a2z9   a2z a2 
+a
b1x7 b1x8 b1x9   b1x   b1y7 b1y8 b1y9   b1y   b1z7 b1z8 b1z9   b1z b1
b2x7 b2x8 b2x9   b2x   b2y7 b2y8 b2y9   b2y   b2z7 b2z8 b2z9   b2z b2 
+b
c1x7 c1x8 c1x9   c1x   c1y7 c1y8 c1y9   c1y   c1z7 c1z8 c1z9   c1z c1
c2x7 c2x8 c2x9   c2x   c2y7 c2y8 c2y9   c2y   c2z7 c2z8 c2z9   c2z c2 
+c
[download]

This does exactly what I need, even though I have a gut feeling that it could be better.

I can live with this solution, if there is nothing else available.

Any paths for improvement?

Can anyone suggest a more linear course of action?

TIA

 _  _ _  _  
(_|| | |(_|><
 _|

In reply to Variant permutation by gmax

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


laziness, impatience, and hubris
	PerlMonks