Print all possible boolean states of n variables in Perl/Java w/o binary

Question

I need to generate all possible boolean states (2^n) of n variables. For example for n=3 it should look like this:

0 0 0  
1 0 0  
0 1 0  
0 0 1  
1 1 0  
1 0 1  
0 1 1  
1 1 1  

Unfortunately I cannot use binary magic, like it is shown here so this (master)piece of simplicity is unusable for me :(

final int n = 3;
for (int i = 0; i < Math.pow(2, n); i++) {
    String bin = Integer.toBinaryString(i);
        while (bin.length() < n)
        bin = "0" + bin;
    System.out.println(bin);
} 

I need to do this in a simple yet efficient way using plain cycles without special things like binary or list functions as shown in the answer above.

Any help would be much appreciated!

Answer 1

what about something like this? Add a comment if something is not clear!

void allConfigurations(int n, int[] config, int index)
{
    if(index == n)// base case, the whole config has been filled
    {
        printConfiguration(config);
        return;
    }
    config[index] = 0; //create config with 0 at index
    allConfigurations(n, config, index + 1);
    config[index] = 1; //create config with 1 at index
    allConfigurations(n, config, index + 1);
}

Answer 2

The states are

sub bits {
   my ($n, $i) = @_;
   return map { my $bit = $i & 1; $i >>= 1; $bit } 0..$n-1;
}

my $n = 3;
for my $i (0 .. (1<<$n)-1) {
   my @bits = bits($n, $i);
   print("@bits\n");
}

If you don't have &, << and >> (which would be really really weird as all CPUs have these), or if you want more than two states, you can use the following:

sub bits {
   my ($b, $n, $i) = @_;
   return map { my $bit = $i % $b; $i = ($i-$bit)/$b; $bit } 0..$n-1;
}

my $n = 3;
my $b = 2;
for my $i (0 .. ($b**$n)-1) {
   my @bits = bits($b, $n, $i);
   print("@bits\n");
}

Optimized:

sub get_next {
   my ($b, $bits) = @_;
   for (@$bits) {
      return 1 if ++$_ != $b;
      $_ = 0;
   }
   return 0;
}

my $n = 3;
my $b = 2;
my @bits = (0) x $n;
while (1) {
   print("@bits\n");
   last if !get_next($b, \@bits);
}

---

Benchmark results for n=3,

                  Rate tommaso_pasini        ikegami ikegami_inline
tommaso_pasini 34462/s             --           -23%           -49%
ikegami        44612/s            29%             --           -34%
ikegami_inline 68061/s            97%            53%             --

Benchmark results for n=10,

                Rate tommaso_pasini        ikegami ikegami_inline
tommaso_pasini 271/s             --           -33%           -58%
ikegami        403/s            48%             --           -38%
ikegami_inline 644/s           138%            60%             --

Benchmarking code:

use strict;
use warnings;
use Benchmark qw( cmpthese );

sub _tommaso_pasini {
    my ($n, $bits, $i) = @_;

    if ($i == $n) {
    # ...
        return;
    }

    $bits->[$i] = 0;
    _tommaso_pasini($n, $bits, $i+1);
    $bits->[$i] = 1;
    _tommaso_pasini($n, $bits, $i+1);
}

sub tommaso_pasini {
   my ($n) = @_;
   _tommaso_pasini($n, [], 0);
}

sub ikegami_next {
   my ($bits) = @_;
   for (@$bits) {
      return 1 if ++$_ != 2;
      $_ = 0;
   }
   return 0;
}

sub ikegami {
   my ($n) = @_;
   my $bits = [ (0) x $n ];
   while (1) {
      # ...
      last if !ikegami_next($bits);
   }
}

sub ikegami_inline {
   my ($n) = @_;
   my $bits = [ (0) x $n ];
   OUTER: while (1) {
      # ...

      for (@$bits) {
         next OUTER if ++$_ != 2;
         $_ = 0;
      }

      last;
   }
}

for my $n (3, 10) {
   cmpthese(-3, {
      ikegami        => sub { ikegami($n)        },
      ikegami_inline => sub { ikegami_inline($n) },
      tommaso_pasini => sub { tommaso_pasini($n) },
   });
}

Answer 3

Just posting the Perl version of the great solution above, in case somebody needs it. @TommasoPasini thanks again!

sub allConfigurations{
    my ($n, $index, @config) = @_;

    if($index == $n) #base case, the whole config has been filled
    {
        &printConfiguration(@config);
        return;
    }
    $config[$index] = 0; #create config with 0 at index
    allConfigurations($n, $index + 1, @config);

    $config[$index] = 1; #create config with 1 at index
    allConfigurations($n, $index + 1, @config);
}

sub printConfiguration{
    my @config = @_;

    print "@config";
    print "\n";
}


&allConfigurations(3, my $index=0, my @conf);