laziness, impatience, and hubris PerlMonks

### Re: Combinatorics of Math::Combinatorics (Loops)

by tye (Cardinal)
 on Jul 22, 2012 at 02:18 UTC ( #983036=note: print w/ replies, xml ) Need Help??

in reply to Combinatorics of Math::Combinatorics

Using some slightly simplified code ripped from a future version of Algorithm::Loops I solved it like this (using an iterator so no worries about memory exhaustion for moderately large inputs):

```my @input = ( 'a' .. 'e' );
my \$max_subset = 3;
my \$iter = NestedLoops(
[ sub { [0] }, ( sub { [ 0 .. 1+\$_ ] } ) x \$#input ],
sub {
return -1  if  \$max_subset < \$_;
return  1  if  @_ == @input;
},
);
my @slots;
while(  @slots = \$iter->()  ) {
my @subsets = ('') x @input;
\$subsets[\$slots[\$_]] .= \$input[\$_]
for 0 .. \$#input;
print "@subsets\n";
}

Producing this output:

```abc de
abc d e
abd ce
abe cd
ab cde
ab cd e
abe c d
ab ce d
ab c de
ab c d e
acd be
ace bd
ac bde
ac bd e
ae bcd
a bcd e
ae bc d
a bce d
a bc de
a bc d e
ae bd c
a bde c
a bd ce
ae b cd
a be cd
a b cde
a b cd e
ae b c d
a be c d
a b ce d
a b c de
a b c d e

Here is the simplified NestedLoops() I used:

```sub NestedLoops
{
my( \$loops, \$when )= @_;

my @list;
my \$i= -1;
my @idx;
my @vals= @\$loops;
my %freq;

return  sub { return }
if  ! @vals;

return  sub {
while( 1 ) {
# Prepare to append one more value:
if(  \$i < \$#\$loops  ) {
\$idx[++\$i]= -1;
local( \$_ )= \$list[-1];
\$vals[\$i]= \$loops->[\$i]->( @list );
}
## return   if  \$i < 0;
my \$act = -1;
while(  \$act < 0  ) {
# Increment furthest value, chopping if done there:
while(  @{\$vals[\$i]} <= ++\$idx[\$i]  ) {
--\$freq{ \$list[\$i] };
pop @list;
return   if  --\$i < 0;
}
\$act = do {
--\$freq{ \$list[\$i] }
if  0 < \$idx[\$i];
local \$_ = ++\$freq{ \$list[\$i]= \$vals[\$i][\$idx[\$i]]
+ };
\$when->( @list );
};
return @list
if  0 < \$act;
}
}
};
}

- tye

Comment on Re: Combinatorics of Math::Combinatorics (Loops)

Create A New User
Node Status?
node history
Node Type: note [id://983036]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (6)
As of 2013-05-19 18:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?