We don't bite newbies here... much PerlMonks

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

by LanX (Sage)
 on Sep 18, 2020 at 08:43 UTC Need Help??

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";
}
}
}

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

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

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 (Sage) 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;
}
}
}

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

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11121899]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (3)
As of 2022-12-09 03:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?