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 );
[download]

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        

With 435 zeroes and 343 ones, you'll never live long enough to see it finish, regardless of the method used to generate the sequence. A simple way to figure out how many permutations a list will generate is with

my $num_zeros = 3; my $num_ones = 2;
use Math::BigInt;
sub fac {
    my $result = Math::BigInt->new("1");
    my $n = Math::BigInt->new(shift());
    while($n){ $result *= $n--; }
    return $result;
}
my $num_permutations = fac($num_ones + $num_zeros ) / (fac($num_ones) 
+* fac($num_zeros));
print("Number of permutations of a ($num_zeros, $num_ones) list is $nu
+m_permutations\n");'
[download]

A list with 453 zeros and 343 ones will have roughly 1.962e230 different permutations -- are you sure you need all of them?

I like this way of computing it better, for several mostly unimportant reasons. :)

#!/usr/bin/perl -w
use strict;

print countPairPermutations( @ARGV ), $/;

sub countPairPermutations
{
    my( $x, $y )= @_;
    ( $x, $y )= ( $y, $x )
        if  $y < $x;
    my $log= 0;
    for my $i (  1 .. $x  ) {
        $log += log( $y+$i ) - log( $i );
    }
    my $exp= int( $log / log(10) );
    my $mant= exp( $log - log(10)*$exp );
    $mant= sprintf "%.*f", 6 < $exp ? 3 : 8, $mant;
    $mant .=  $exp  ?  "e" . $exp  :  "";
    return $mant
        if  6 < $exp;
    return 0 + $mant;
}
[download]

My code appears to agree with your code (though I didn't count the number of digits output by your code) but they both disagree with your node, reporting that there are 5.807e234 different permutations (not 1.962e230).

Update: Or, using my prototype module:

#!/usr/bin/perl -w
use strict;
require Math::BigPositiveOkayPrecision;

print countPairPermutations( @ARGV ), $/;

sub countPairPermutations
{
    my( $x, $y )= @_;
    ( $x, $y )= ( $y, $x )
        if  $y < $x;
    my $p= Math::BigPositiveOkayPrecision->new( 1 );
    for my $i (  1 .. $x  ) {
        $p= $p * ( $y+$i ) / $i;
    }
    return $p;
}
[download]

- tye        

Perhaps if you told us what you were trying to achieve we might understand what it is that you actually need. Up to now every time someone suggests a new solution you have introduced a new requirement.

Tell us what you need this for and what the constraints are on the input parameters and what the requirements are for the output.

A fairly trivial change to the recursive code I gave will change it to work with a string of characters rather than a "string" of bits. You would still run into deep recursion issues with large numbers of ones and other solutions are likely to be faster (memory constraints on recursion are unlikely to be a factor though) however.

---

DWIM is Perl's answer to Gödel