Re^4: One Zero variants_without_repetition

[papidave]

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...

[tye]

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."