Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

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
in thread 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        

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://631068]
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
Find Nodes?
    Voting Booth?