Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question: 

#print all combinations of 6 ones and 12 zeros
for( 0b000000000000111111..0b111111000000000000 )
{
    my $x = sprintf("%018b",$_);
    next unless $x =~ /^0*10*10*10*10*10*10*$/;
    printf "$x\n",$_;
}

[download]

Edit Masem 2002-02-19 - Added CODE tags, changed title from "Is there a faster way to do this?"

Replies are listed 'Best First'.
Re (tilly) 1: Is there a faster way to do this?
by tilly (Archbishop) on Feb 18, 2002 at 02:10 UTC
    Fast code and maintainable code are often contrary goals. 
    use strict;
my $row = join '', map '0', 1..18;
$row .= "\n";
for my $i_1 (0..12) {
  substr($row, $i_1, 1, 1);
  for my $i_2 (($i_1+1)..13) {
    substr($row, $i_2, 1, 1);
    for my $i_3 (($i_2+1)..14) {
      substr($row, $i_3, 1, 1);
      for my $i_4 (($i_3+1)..15) {
        substr($row, $i_4, 1, 1);
        for my $i_5 (($i_4+1)..16) {
          substr($row, $i_5, 1, 1);
          for my $i_6 (($i_5+1)..17) {
            substr($row, $i_6, 1, 1);
            print $row;
            substr($row, $i_6, 1, 0);
          }
          substr($row,$i_5, 1, 0);
        }
        substr($row, $i_4, 1, 0);
      }
      substr($row, $i_3, 1, 0);
    }
    substr($row, $i_2, 1, 0);
  }
  substr($row, $i_1, 1, 0);
}

    [download]
    My next try at getting faster would be to go to Inline.
[reply]
[d/l]
Re: Is there a faster way to do this?
by I0 (Priest) on Feb 18, 2002 at 02:51 UTC 
    for(
  $_=0b000000000000111111;
  ($x=$_)<=0b111111000000000000;
  $x&=~$x>>1,$x&=-$x,$_+=$x--,($x&=$_)?($_-=$x,$_+=$x/($x&-$x)):0
){
    printf "%018b\n",$_
}

    [download]
[reply]
[d/l]
Re: Is there a faster way to do this?
by cLive ;-) (Prior) on Feb 18, 2002 at 02:14 UTC
    Not declaring a new variable speeds it up by a reasonable amount - and dropping the unneeded printf: 
    for( 0b000000000000111111..0b111111000000000000 ) {
  $_ = sprintf("%018b",$_);
  next unless /^0*10*10*10*10*10*10*$/;
  print "$_\n";
}

    [download]

    cLive ;-)

    --
    seek(JOB,$$LA,0);

[reply]
[d/l]
Re: Is there a faster way to do this?
by belg4mit (Prior) on Feb 18, 2002 at 01:48 UTC
    I'd try to Permute (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1). Then sort (no need to supply a sort routine), and unique the resulting list. Be careful though not to use a hash (collision city!) to do the uniqeing, rather simply tracking and comparing against the previous value.

    UPDATE: And I'd have made the problem worse. That turns it into a factorial or 18! which is 6_402_373_705_728_000 permutations. (Even with the most efficient means I can think of to store this, pack it and push the result onto an array, it'd be 14,000 terabytes, not counting the internal overhead for the data structure. *sigh*). This comes about (and is why a uniq and sort would be necessary) because we have elements which are indistinguishable from one another. In the 425756 permutations I generated I had 420376 duplicates, or only 5380 results.

    --
    perl -pe "s/\b;([st])/'\1/mg"

[reply]

Back to Seekers of Perl Wisdom