Re: Speeding permutation counting

albert,
I found this a neat an interesting problem but I haven't had a chance to try out my idea. I do have a couple of questions first:

Do you need the count breakout per position or just total over all strings?
With 010 and 101, should the count of "01" and "10" be 2 per position for a total of 6? In other words, do each strings need to be compared twice taking turns being on top?

I don't think any answer to the questions would invalidate my idea but it might change the implementation a bit. Since I do not have time to try it myself, I am laying it out here.

I believe you should be able to mathematically determine the counts without doing the comparisons. I believe all you need to do is count how many 0s and 1s there are for each position. To further speed up the process, I might even consider doing the counting using Inline::C.

Cheers - L~R

Comment on Re: Speeding permutation counting

Replies are listed 'Best First'.
Re^2: Speeding permutation counting by BrowserUk (Patriarch) on Jul 19, 2007 at 20:20 UTC
If you just need to count the number of set bits there is no need to drop into Inline C. This example from perlfunc unpack 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."	[reply] [d/l]
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]
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. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply]
Re^5: Speeding permutation counting by Limbic~Region (Chancellor) on Jul 20, 2007 at 00:08 UTC
Re^6: Speeding permutation counting by BrowserUk (Patriarch) on Jul 20, 2007 at 00:19 UTC
Some notes below your chosen depth have not been shown here