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

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

Replies are listed 'Best First'.
Re^4: Speeding permutation counting
by BrowserUk (Patriarch) on Jul 19, 2007 at 21:15 UTC

    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]

        What the OP is calculating is the number of bit pairing (4 values) for each combination of 2 strings.

        Eg: Assuming 32-bit strings, typical values might be: 

        strings: '00'   '01'    '10'    '11'
1 & 2     10      5      12      15
1 & 3      2     17       7       6
1 & 4    
1 & 5 
2 & 3 ....

        [download]

        So the OP wants 4 numbers per pairing of strings, regardless of the number of bits.

        What you would be calculating is 4 numbers per bit position, regardless of the number 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]
[d/l]

In Section Seekers of Perl Wisdom