Re^2: Speeding permutation counting

BrowserUk,
Once I understood the problem, I came up with a solution very similar to yours. When I logged in this morning, I noticed that you had already came up with the idea. Why does work have to get in the way of fun?

I doubt there would be a speed improvement but I am pretty sure you only have to count '01' since '10' is just a reflection. Additionally, you should only need to calculate ('11' and '00') or ('11' and '10') or ('00' and '10'). The remaining two can be obtained with math.

Cheers - L~R

Comment on Re^2: Speeding permutation counting

Replies are listed 'Best First'.
Re^3: Speeding permutation counting by albert (Monk) on Jul 21, 2007 at 23:38 UTC
In my problem '01' is different than '10', and I need to count them separately. Still, your point of not needing to count the last is well taken, as I can count 3, and thereby know the 4th. However, by doing this, I'm not seeing any significant performance gains, and it may be a bit slower. `Rate browser+LR browserUK browser+LR 19055/s -- -2% browserUK 19509/s 2% --` [download] Code for benchmarking... #!/usr/bin/perl use strict; use Benchmark qw/cmpthese/; cmpthese( -3, { # orighash => sub { orighash(); }, # twolevel => sub { twolevel(); }, # substring => sub { substring(); }, # blokhead => sub { blokhead(); }, #blokchop => \&blokchop, #orig => \&orig, browserUK => \&browserUK, "browser+LR" => \&browserLR, #ikegami => \&ikegami, } ); sub browserUK { my @strings = qw/111011001010011110100010100001 111010000010010110000010000001 000101011100001000110101110000 000101111101001001111101111110 111011001010111110100010100001 000100010100000000010001010000/; for my $i ( 0 .. $#strings ) { for my $j ( $i + 1 .. $#strings ) { my @counts = ( ( $strings[$i] \| $strings[$j] ) =~ tr[0][0], ( ~$strings[$i] & $strings[$j] ) =~ tr[\1][\1], ( $strings[$i] & ~$strings[$j] ) =~ tr[\1][\1], ( $strings[$i] & $strings[$j] ) =~ tr[1][1] ); } } } sub browserLR { my @strings = qw/111011001010011110100010100001 111010000010010110000010000001 000101011100001000110101110000 000101111101001001111101111110 111011001010111110100010100001 000100010100000000010001010000/; for my $i ( 0 .. $#strings ) { for my $j ( $i + 1 .. $#strings ) { my @counts = ( ( $strings[$i] \| $strings[$j] ) =~ tr[0][0], ( ~$strings[$i] & $strings[$j] ) =~ tr[\1][\1], ( $strings[$i] & ~$strings[$j] ) =~ tr[\1][\1], # ( $strings[$i] & $strings[$j] ) =~ t +r[1][1] ); $counts[3] = scalar(@strings) - $counts[0] - $counts[1] - +$counts[2]; } } } [download]	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: Speeding permutation counting
by albert (Monk) on Jul 21, 2007 at 23:38 UTC

              Rate browser+LR  browserUK
browser+LR 19055/s         --        -2%
browserUK  19509/s         2%         --
[download]

#!/usr/bin/perl

use strict;
use Benchmark qw/cmpthese/;

cmpthese(
    -3,
    {

        #        orighash  => sub { orighash(); },
        #         twolevel  => sub { twolevel(); },
        #        substring => sub { substring(); },
        #        blokhead  => sub { blokhead(); },
        #blokchop     => \&blokchop,
        #orig         => \&orig,
        browserUK    => \&browserUK,
        "browser+LR" => \&browserLR,
        #ikegami      => \&ikegami,
    }
);

sub browserUK {
    my @strings = qw/111011001010011110100010100001
      111010000010010110000010000001
      000101011100001000110101110000
      000101111101001001111101111110
      111011001010111110100010100001
      000100010100000000010001010000/;

    for my $i ( 0 .. $#strings ) {
        for my $j ( $i + 1 .. $#strings ) {
            my @counts = (
                ( $strings[$i] | $strings[$j] )  =~ tr[0][0],
                ( ~$strings[$i] & $strings[$j] ) =~ tr[\1][\1],
                ( $strings[$i] & ~$strings[$j] ) =~ tr[\1][\1],
                ( $strings[$i] & $strings[$j] )  =~ tr[1][1]
            );
        }
    }

}

sub browserLR {
    my @strings = qw/111011001010011110100010100001
      111010000010010110000010000001
      000101011100001000110101110000
      000101111101001001111101111110
      111011001010111110100010100001
      000100010100000000010001010000/;

    for my $i ( 0 .. $#strings ) {
        for my $j ( $i + 1 .. $#strings ) {
            my @counts = (
                ( $strings[$i] | $strings[$j] )  =~ tr[0][0],
                ( ~$strings[$i] & $strings[$j] ) =~ tr[\1][\1],
                ( $strings[$i] & ~$strings[$j] ) =~ tr[\1][\1],

                #                ( $strings[$i] & $strings[$j] )  =~ t
+r[1][1]
            );
            $counts[3] = scalar(@strings) - $counts[0] - $counts[1] - 
+$counts[2];
        }
    }

}
[download]

[reply]
[d/l]
[select]