Non- recursive permutation of arrays.

[shotgunefx]

Description:

Takes a list or array of array references and returns a function that will return successive permutations of the referenced arrays. Avoids recursion so will work on abitrarily huge sets of data. Runtime scales linearly with the number of sets. Minimal memory usage.

my @aoa = (
    [('a'..'z')],
    [('A'..'Z')],
    [(1..26)],
);


my $iter = make_permutator(@aoa);


while (my @els = $iter->() ){
    print @els,"\n";
}


sub make_permutator{
    my @arefs = @_;
    my @arrayindexes = ();
    foreach (@arefs){
        push @arrayindexes,[$_,0,$#{$_}];
    }
    
    return sub {
            return if $arrayindexes[0]->[1] > $arrayindexes[0]->[2]; 
            my @els =  map { $_->[0]->[ $_->[1]] } @arrayindexes;
            # Check for out of bounds....
            $arrayindexes[$#arrayindexes]->[1]++;
            for (my $i = $#arrayindexes; $i > 0; $i--){
                    if ($arrayindexes[$i]->[1] > $arrayindexes[$i]->[2
+]){
                        $arrayindexes[$i]->[1] = 0;
                        $arrayindexes[$i-1]->[1]++;
                    }else{
                        last;
                    }
            }
            return @els;
            
    };
}

[ariels]

Or, you could just count up to the product of the array sizes, and use the count to compute the offsets into the arrays (I think a note described this, but no code). If you have lists of lengths l₁,...,l_k, think of the numbers 0..(l₁*...*l_k-1). You want to convert them to a variable-base number system, where the first digit can be 0..l₁-1, the second digit can be 0..l₂-1,...

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

my @aoa = (
       [('a'..'f')],
       [('A'..'C')],
       [(1..2)],
      );


my $iter = make_permutator(@aoa);


while (my @els = $iter->() ){
  print "@els\n";
}


# ariels' code from here
sub make_permutator {
  use integer;
  my @idx_link = (0, @_);
  return sub {
    my $idx = $idx_link[0]++;
    my @ret;
    for my $i (1..$#idx_link) {
      push @ret, $idx_link[$i][$idx % @{$idx_link[$i]}];
      $idx /= @{$idx_link[$i]};
    }
    return $idx ? () : @ret;
  }
}

[shotgunefx]

Interesting take. That way solution wouldn't have occured to me. I do think it's a bit more obfu though. I had to stare at it for a minute (Maybe just me though!). The best thing (IMHO) about Perl is how many different ways you can accomplish a single goal.

-Lee

"To be civilized is to deny one's nature."