On 14/07/2012 18:22, joeu2004 wrote:
"Peter T" wrote:
Now if you can derive some formula that returns 16431
for the filtered '4 out of 6' that would validate my routine!

I have tried to count this in the past, and I believe I never succeeded.

That is why I would like to see your 16,431 combinations.

My algorithm generated 2240; and I do not see any mistake (yet). I
posted a pointer to my uploaded file in another response.

My algorithm also generated 2240 for the base case with no repetitions
using a greedy take exactly 15 matches at a time only approach with a
starting seed value of 0x3f = 63 = 00111111b first time around.

But if I choose a random 6 bits are 1 starting seed instead I can get
slightly different values - best so far is from 0x333 = 1100110011b with
2244 hits followed by 0xAAA = 101010101010b with 2242 hits and the worst
so far 0x111111 with only 2233 hits.

I wonder if there is some neat way to generate manually by construction
a better set of test patterns instead of the entire 6/36 ~2M entries.
The closest I can think of is to use the structure of the problem 6C36
and treat it at a nested case of 3C6 6 bit long patterns placed in 2C12
positions and zero padded. (And also 6 bits all set in 6 positions)

3C6 = 6!/3!^2 = 20
2C12 = 12.11/2 = 76

My back of the envelope reasoning is that the 3C6 binary patterns can
have at most 2 matching bits in common and so the subset this generates
which contains 76.20.20 = 30400 elements all have less than or equal to
4 matching bits and might therefore stand a better chance of spanning
the space more efficiently than the brute force greedy method.

I haven't thought of a neat way to set the problem up that will allow an
efficient search of the very large space for a global optimum. Like you
I think the greedy method may not be optimal but cannot prove it.

So far my results are by trial and error.

--
Regards,
Martin Brown