### Re^4: One Zero variants_without_repetition

by papidave (Pilgrim)
 on Aug 07, 2007 at 15:08 UTC ( #631068=note: print w/replies, xml ) Need Help??

in reply to Re^3: One Zero variants_without_repetition

GrandFather spake it well; this question maps quite well into a recursive algorithm:
```sub combinatoric(\$\$); # prototype forward reference

sub combinatoric( \$\$ )
{
my ( \$zero, \$one ) = @_;

my @ret = ();
if ( \$one == 0 )
{
# no more ones left to select, the rest is zeroes.
push @ret, scalar ( '0' x \$zero );
}
elsif ( \$zero == 0 )
{
# no more zeroes left to select, the rest is ones.
push @ret, scalar ( '1' x \$one );
}
else
{
# take a zero from the pile, and compute what's left
push @ret, "0\$_" foreach combinatoric( \$zero-1, \$one );
# take a one from the pile, and compute what's left
push @ret, "1\$_" foreach combinatoric( \$zero, \$one-1 );
}
return @ret;
}

print "\$_\n" foreach combinatoric( 10, 10 );
I was quite surprised to see how quickly the 10, 10 case started giving results, even on a lowly 2.4GHz Xeon...

Replies are listed 'Best First'.
Re^5: One Zero variants_without_repetition (reversion from recursion)
by tye (Sage) on Aug 07, 2007 at 16:29 UTC

Recursion scales very, very poorly. Given that thenetfreaker has reported that several hundred bits are involved, any of the recursive solutions in this thread will surely run out of memory before producing a single result (for that size of problem). The iterators, however, immediately produce the first result and never use much memory at all.

Update: I think only the immediately above solution tries to return all of the answers in one big list (as I'm used to recursive solutions doing). So some other solutions (both recursive and not) just require a call-back be used (or the code to process each item be in-lined), which is inconvenient compared to using an interator but not a "show stopper."

- tye

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

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2020-01-22 16:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The worst excuse I have ever heard is:

Results (102 votes). Check out past polls.

Notices?