Re: Looking for combinatorics with state

[BrowserUk]

This is a modification of my nFor function from years ago.

# ! perl -slw
use strict;

sub nForS(&$@) {
    my $code = shift;    die "First argument must be a code ref"   unl
+ess ref( $code ) eq 'CODE';
    my $aref = shift;    die "second argument must be an array ref" un
+less ref( $aref ) eq 'ARRAY';

    my @limits = @_;

    our @indices; local *indices = $aref;

    @indices = ( 0 ) x @limits unless @indices;

    for( my $i = $#limits; $i >= 0; ) {
        $i = $#limits;
        $code->( @indices ), ++$indices[ $i ]
            while $indices[ $i ] < $limits[ $i ];
        $i = $#limits;
        $indices[ $i ] = 0, ++$indices[ --$i ]
            while $i >= 0 and $indices[ $i ] == $limits[ $i ];
    }
}

my @state;
my $n = 10;
nForS{ print "@_\n"; last unless --$n } \@state, 3, 6, 9;

print "First 10 permutations; enter to see the rest"; <STDIN>;

nForS{ print "@_\n"; } \@state, 3, 6, 9;

Outputs:

C:\test>junk
0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 1 0
First 10 permutations; enter to see the rest
0 1 0
0 1 1
0 1 2
0 1 3
...
2 5 6
2 5 7
2 5 8

That just demonstrates that you can save and restore that state of the iterators.

The basics of the nFor are that it doesn't iterate the data, but iterates indices, which you then use to slice the data. Eg.

# ! perl -slw
use strict;

sub nForS(&$@) {
    my $code = shift;    die "First argument must be a code ref"   unl
+ess ref( $code ) eq 'CODE';
    my $aref = shift;    die "Second argument must be an array ref" un
+less ref( $aref ) eq 'ARRAY';

    my @limits = @_;

    our @indices; local *indices = $aref;

    @indices = ( 0 ) x @limits unless @indices;

    for( my $i = $#limits; $i >= 0; ) {
        $i = $#limits;
        $code->( @indices ), ++$indices[ $i ]
            while $indices[ $i ] < $limits[ $i ];
        $i = $#limits;
        $indices[ $i ] = 0, ++$indices[ --$i ]
            while $i >= 0 and $indices[ $i ] == $limits[ $i ];
    }
}

my @state;

my @alpha =  'a'..'z';
my @nums = 10 .. 20;
my @rands = map rand, 1 .. 10;

my $n = 23;
nForS{
    print "$alpha[ $_[0] ] $nums[ $_[1] ] $rands[ $_[2] ] \n";
    last unless --$n;
} \@state, 26, 11, 10;

print "First 23 perms; enter to continue"; <STDIN>;

nForS{
    print "$alpha[ $_[0] ] $nums[ $_[1] ] $rands[ $_[2] ] \n";
} \@state, 26, 11, 10;

__DATA__
C:\test>junk
a 10 0.69268798828125
a 10 0.297698974609375
a 10 0.94830322265625
a 10 0.024749755859375
a 10 0.934661865234375
a 10 0.614898681640625
a 10 0.361328125
a 10 0.20947265625
a 10 0.556488037109375
a 10 0.879547119140625
a 11 0.69268798828125
a 11 0.297698974609375
a 11 0.94830322265625
a 11 0.024749755859375
a 11 0.934661865234375
a 11 0.614898681640625
a 11 0.361328125
a 11 0.20947265625
a 11 0.556488037109375
a 11 0.879547119140625
a 12 0.69268798828125
a 12 0.297698974609375
a 12 0.94830322265625
First 23 perms; enter to continue
a 12 0.94830322265625
a 12 0.024749755859375
a 12 0.934661865234375
a 12 0.614898681640625
a 12 0.361328125
a 12 0.20947265625
a 12 0.556488037109375
...

As you can imagine, with all the indirection, nFor() isn't fast, but it is supremely flexible.