in reply to Re: Speeding permutation counting
in thread Speeding permutation counting

If you just need to count the number of set bits there is no need to drop into Inline C. This example from perlfuncunpack will do that quite efficiently: 

my $setBits = unpack("%32b*", $strings[ $i ];

[download]

but I don't see how you get from that to the 4 numbers the OP wants?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^3: Speeding permutation counting
by Limbic~Region (Chancellor) on Jul 19, 2007 at 20:46 UTC
    BrowserUk,
    What I am suggesting is that if you know the number of 1s and 0s in all strings in position 1, you should be able to calculate the number of '11', '00', '10', and '01' at position 1 without comparing any of the strings. This would still have to be done for all strings at all positions - I am just trying to eliminate the comparisons.

    Cheers - L~R

[reply]

      Oh. I see what you mean.

      Eg. If of 1000 strings, 500 have a 1 in bit 0, then you know that in the 500500 2-way compares, you would get '00' & '11' 1/4 of the time each and '01' or '10' 1/2 of the time.

      But I don't see a way of determining how many '10's relative to the '01's?

      And no way to determine which pairs of strings render which values for any given bit, nor a count of the four possible values for any given pair of strings?

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
        BrowserUk,
        I am likely misunderstanding the problem. For the sake of simplicity, I am using strings of 1 character. Do I have the correct output for the provided input? 
        string 1: 0
string 2: 1
string 3: 0
string 4: 1
string 5: 0

1 & 2 -> 01 10
1 & 3 -> 00 00
1 & 4 -> 01 10
1 & 5 -> 00 00
2 & 3 -> 10 01
2 & 4 -> 11 11
2 & 5 -> 10 01
3 & 4 -> 01 10
3 & 5 -> 00 00
4 & 5 -> 10 01

Totals

01 = 6
10 = 6
11 = 2
00 = 6

        [download]
        If that is correct, then I think my math approach will work.

        Cheers - L~R

[reply]
[d/l]

In Section Seekers of Perl Wisdom