Re: Generate all unique combinations of 1 and 0 using specified length of "0"-string and count of 1's

There is a straight forward solution if the numbers of 1s are fixed.

I've realized too late that that number is supposed to be free too, so you need recursion (or fake it).

For completeness:

use strict;
use warnings;
use 5.12.0;

my $len = 5;
my $max = $len - 1;

for my $p0 ( 0 .. $max ) {
    for my $p1 ( $p0+1 .. $max ) {
        for my $p2 ( $p1+1 .. $max ) {
            my $str = "0" x $len;
            substr $str, $p0, 1, '1';
            substr $str, $p1, 1, '1';
            substr $str, $p2, 1, '1';
            say "$str $p0 $p1 $p2";
        }
    }
}
[download]

C:/Perl_524/bin\perl.exe -w d:/tmp/pm/bitstrings.pl 11100 0 1 2 11010 0 1 3 11001 0 1 4 10110 0 2 3 10101 0 2 4 10011 0 3 4 01110 1 2 3 01101 1 2 4 01011 1 3 4 00111 2 3 4 Compilation finished at Fri Sep 18 10:43:25
[download]

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

Comment on Re: Generate all unique combinations of 1 and 0 using specified length of "0"-string and count of 1's Select or Download Code

Replies are listed 'Best First'.

Re^2: Generate all unique combinations of 1 and 0 using specified length of "0"-string and count of 1's
by LanX (Saint) on Sep 19, 2020 at 15:38 UTC

> so you need recursion (or fake it).

so here a recursive version with global variables (because I also wanted to provide a solution with two nested loops "faking" recursion, but gave up)

NB: it's optimized for the dual case, where it's easier to set 0s into a string full of 1s.

use 5.12.0;
use strict;
use warnings;
use Data::Dump qw/pp dd/;
use Test::More;


my $ones = 3;
my $len = 5;

my @res;
my ($zero,$one) = ('0','1');

# optimize dual case
if ($ones > $len/2) {
    ($zero,$one) = ($one,$zero);
    $ones = $len-$ones;
}

my $max = $len - 1;
our $str = $zero x $len;
our $level = 0;

rec(0);
pp \@res;


sub rec {
    local $level = $level + 1;
    my ($start) =@_;
    for my $idx ( $start .. $max ) {
        local $str = $str;
        substr $str, $idx, 1, $one;
        if ($level < $ones) {
            rec( $idx + 1 );
        } else {
            push @res, $str;
        }
    }
}
[download]

[ "00111", "01011", "01101", "01110", 10011, 10101, 10110, 11001, 11010, 11100, ]
[download]

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

[reply]
[d/l]
[select]


Clear questions and runnable code get the best and fastest answer
	PerlMonks