Re^2: One Zero variants_without_repetition

[thenetfreaker]

i changed a bit you code to :

my $places = 6;
for my $left (1..$places-1) {
    for my $right (0 .. $left -1) {
        printf "%0$places"."b\n", (1 << $left) | (1 << $right);
    }
}

and saw it works only with 2 ones...

and what if i have 6 ones and 14 zeroes ? do i have to do 6 for() loops ???

[GrandFather]

Recursion:

use strict;
use warnings;

doShift (2, 5);
print "\n";
doShift (3, 6);
print "\n";


sub doShift {
    my ($ones, $bits, $pattern, $limit) = @_;
    
    --$ones;
    $limit ||= $bits;
    $pattern ||= 0;
    
    for my $right ($ones .. $limit - 1) {
        if ($ones) {
            doShift ($ones, $bits, $pattern | (1 << $right), $right);
        } else {
            printf "%0*b\n", $bits, $pattern | (1 << $right);
        }
    }
}

Prints:

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011
100101
100110
101001
101010
101100
110001
110010
110100
111000

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

[thenetfreaker]

That's nice, but it goes through the factorial of $ones+$zeroes, 5!=120.. 120 != 10.
i'm working with strings of 435 zeroes and 343 ones (for instance), where i'm in dought i'll live that long to see it finish.

i need this sub{} to play with the strings that contain that number of 1's and 0's, not the numbers that contain them.

[ohcamacj]

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");'

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

[GrandFather]

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.