2
$\begingroup$

I'm making some exercises on combinatorics algorithm and trying to figure out how to solve the question below:

Given a group of 25 bits, set (choose) 15 (non-permutable and order NON matters):

n!/(k!(n-k)!) = 3.268.760 

Now for every of these possibilities construct a matrix where I cross every unique 25bit member against all other 25bit member where in the relation in between it there must be at least 11 common setted bits (only ones, not zeroes).

Let me try to illustrate representing it as binary data, so the first member would be:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits) 0000000001011111111111111 second member 0000000001101111111111111 third member 0000000001110111111111111 and so on....  ... 1111111111111110000000000 up to here. The 3.268.760 member. 

Now crossing these values over a matrix for the 1 x 1 I must have 15 bits common. Since the result is >= 11 it is a "useful" result.

For the 1 x 2 we have 14 bits common so also a valid result.

Doing that for all members, finally, crossing 1 x 3.268.760 should result in 5 bits common so since it's < 11 its not "useful".

What I need is to find out (by math or algorithm) wich is the minimum number of members needed to cover all possibilities having 11 bits common.

In other words a group of N members that if tested against all others may have at least 11 bits common over the whole 3.268.760 x 3.268.760 universe.

Using a brute force algorithm I found out that with 81 25bit member is possible achive this. But i'm guessing that this number should be smaller (something near 12).

I was trying to use a brute force algorithm to make all possible variations of 12 members over the 3.268.760 but the number of possibilities it's so huge that it would take more than a hundred years to compute (3,156x10e69 combinations).

I've googled about combinatorics but there are so many fields that i don't know in wich these problem should fit.

So any directions on wich field of combinatorics, or any algorithm for these issue is greatly appreciate.

PS: Just for reference. The "likeness" of two members is calculated using:

(Not(a xor b)) and a

After that there's a small recursive loop to count the bits given the number of common bits.

  • 0
    It's a little difficult to understand - for me, at least. Perhaps (besides polishing your english) you should state the problem with smaller numbers.2012-04-09
  • 0
    @leonbloy (sorry for the poor English. It's not my native language) Anyway, if you have any suggestions you may eventually try the same problem with small numbers (such as 7 choose 4 matching 3). Despite of all text the focus is on this paragraph: _"... a group of N members that if tested against all others may have at least 11 bits common over the whole 3.268.760 x 3.268.760 universe."_2012-04-09
  • 1
    Say $A$ is the set of your 3.268.760 elements (25 bits with 15 ones). You want to find some (as small as possible) subset $B \subset A$ such that, for all $a \in A$ there exists some $b \in B$ that it has at least 11 ones in common with $a$. Is this correct?2012-04-10
  • 0
    That's correct @leonbloy. [This image](http://universeconquer.webcindario.com/LF.g.s.2012.04.07_025145.png) contains the visual information of the relation strength in between the first 4096 elements. (red meaning high 15bit relation to green meanning 11bit connections). Thanks.2012-04-10
  • 0
    This kind of problem is not easy, but a lot of work has been done, in relation to binary codes with error correction. In that context: you want to cover your full code space (vertices of an hypercube of dimension 25 restricted to a fixed 'weight' = 15) with a covering distance of 4 (number of bits that differ). You should look for some specialization of the http://en.wikipedia.org/wiki/Hamming_bound for fixed weight words.2012-04-10

1 Answers 1