Welcome to the Monastery PerlMonks

### Re: combinations of VARYING multiple arrays

by SimonClinch (Deacon)
 on Nov 18, 2010 at 14:53 UTC ( #872264=note: print w/replies, xml ) Need Help??

in reply to combinations of VARYING multiple arrays

The set of numbers from 0 to 2^N-1 represents all combinations of N items. 0 represents the empty combination and 2^N-1 is the complete combination of all N items. So we already cycle through the possibilities for a single set just by adding 1 and unpacking the number from binary into a selection mask. To iterate all combinations selected from a tree instead of a flat set, without flattening the selections, we therefore simply have to extend the concept of a register or memory address or scalar in perl to be a matching tree of values. This can be done simply by adding an extra scalar at each node of the structure, we'll call this a combination register, and incrementing it with the carry rule that when it reaches 2^N-1 (where N is the number of elements locally in the set)it reverts to zero and one is added to the parent's combination register. When the outer register reaches 2^N+1 (N being the local cardinality), all combinations will have been iterated. So for example, if a local combination register has value 5, this unpacks to 0 ... 0 1 0 1, so we select the first and third items in the local list as the current combination. These have substructures to be iterated as well of course. When they have been exhaustively iterated by simple recursion we increment and go to 6 = 1 1 0 and repeat until the local register reaches 2^N+1. If it is a low level register, we will set back to 0, the parent will increment and if below its 2^N+1 and then reiterate us through all our local combinations. For example:-
```
package testpack;

sub new {
my \$ppref = {};
my \$instance = { TSTPRFL => \$ppref };

%\$ppref
= ( configid => { good => { 'identifier' => [ { 'goodconfig' => 0}
+,
],
},
bad => { 'identifier' => [ { '987nonexist789' => 13},
],
},
},
fileonly => { good => { 'file' => [ {'testfilename.tst' => 0},
+ ]
},
=> '',
'987nonexist789.tst' => 1,
},
},
fullpath1 => {good => { '/home/me/testfiles/testfilename.tst'
=> 0,
},
bad => { '987nonexist789.tst' => 1,
'testfilename.tst' => '',
},
},
# and so on for all testcases
);

return bless \$instance;
}

sub tst {
my \$self = shift;
my %opts = @_;

my \$script = \$opts{ script };
\$self -> infest( \$opts{ options } );
\$self -> { options } = \$opts{ options };
do {
\$self -> tstCombi;
} while( \$self -> nextCombi );
}

sub tstCombi {
my \$self = shift;
# the combination to be tested here is
# indicated by the current mask values in the
# test configuration structure you created and
# then infested with combination registers and maxima
}
sub infest { # infest a structure with combination registers
# and pre-count each set for efficiency and store its max of
+2**N-1

my \$self = shift;
my \$ref = shift;

my \$count = 0;
if ( ref( \$ref ) eq 'HASH' ) {
while ( my ( \$k, \$v ) = each %\$ref ) {
\$self -> infest( \$v );
\$k =~ /^\_/ or \$count++;

}
\$ref -> { _reserved_combi } = 0;
\$ref -> { _reserved_limit } = (2**\$count) - 1 ;
}
elsif ( ref( \$ref ) eq 'ARRAY' ) {
for my \$v ( @\$ref ) {
\$self -> infest( \$v );
ref( \$v ) eq 'SCALAR' and \$count++;
}
push @\$ref, { _reserved_combi => 0,
_reserved_limit => ( 2 ** \$count ) - 1  };
}

}

sub nextCombi {
my \$self = shift;
\$self -> increment ( \$self -> { options } );
}

sub increment {
my \$self = shift;
my \$node = shift;
if ( ref( \$node ) eq 'HASH' ) {
for my \$k ( sort ( grep !/^\_/, ( keys %\$node ))) {
\$self -> increment( \$node -> { \$k } )
and return 1;
}
if ( \$node -> { _reserved_combi } == \$node -> { _reserved_limi
+t } ) {
return ( \$node -> { _reserved_combi } = 0 );
}
else {
return ( \$node -> { _reserved_combi } ++ );
}
elsif ( ref( \$node ) eq 'ARRAY' ) {
if ( \$node -> [ \$#node ]{ _reserved_combi }
== \$node -> [ \$#node ]{ _reserved_limit } ) {
return ( \$node -> [ \$#node ]{ _reserved_combi } = 0 );
}
else {
return ( \$node -> [ \$#node ]{ _reserved_combi } ++ );
}
}
die "something went wrong with the structure";
}
1;

One world, one people

Create A New User
Node Status?
node history
Node Type: note [id://872264]
help
Chatterbox?
 erix .oO( apparently but does not GotToBFast ) [Discipulus]: now i must come back to my house/hoven monks: dont do interesting discussion in my absence! [erix]: or apparently, now it does :) [GotToBTru]: heh erix prods ambrus to (re-)start cbstream... [GotToBTru]: I've got a program with an if ... or ... statement with 80 clauses [stevieb]: 80 clauses? dispatch table? [GotToBTru]: no, lookup [stevieb]: no, I mean have you considered using a dispatch table. an 80 condition if/else is huge :) [GotToBTru]: that is how this should have been done, no question

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (11)
As of 2017-06-22 12:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (519 votes). Check out past polls.