2
$\begingroup$

Let's suppose I want to generate n equal sized boolean arrays with maximum "difference". - "Difference" in this case is defined as that the arrays share as low as possible fields with one another. (an example of share: array1 = {1,0,0,0) and array2 = {1,1,1,1} -> array1 and array2 share 1 field (array1[0] / array2[0])

Just for example: n would equal 2 and the size of the field would be 6 -> the optimum solution would be the arrays [0,0,0,0,0,0],[1,1,1,1,1,1] because they share no fields and so are very "different" from one another Another example: n was equal to 4 and the size of the array would be 4 -> a solution would be [0,0,0,0], [1,1,1,1], [1,1,0,0], [0,0,1,1] - the arrays share 1.33 fields per array by average

Has anybody an idea of an algorithm or solution strategy that could solve this problem (generate n of these arrays) perfectly (or very good - so that they are as different as possible) (in a realistic runtime)? Thanks very much in advance :D

$\endgroup$
7
  • $\begingroup$ I have no idea what you're asking. Try again. $\endgroup$ Sep 30, 2015 at 19:52
  • $\begingroup$ @Yuval Filmus I'm very sorry - I added some examples and explained the problem in greater detail to make it easier to understand. And sorry for mistakes, english is not my native language $\endgroup$
    – user40448
    Sep 30, 2015 at 20:10
  • 1
    $\begingroup$ Just to make sure – what you are after is as large an average as possible? $\endgroup$ Sep 30, 2015 at 20:14
  • $\begingroup$ not really ^^ - if you take the sum of the numbers of fields one array shares with all the others and divide that by the number of "other arrays" you get a value that shows how equal one array is to all the others. If you average all these "inner averages" you get one number that shows how similar all the fields are to one another (so this value is a measurement of the "difference" of the the arrays (the lower the "total average" the more difference and the better)) - sry if it was/is confusing and badly explained $\endgroup$
    – user40448
    Oct 1, 2015 at 18:59
  • $\begingroup$ We can't guess what you mean when you ask a question unless you explain yourself clearly. From now on you're on your own. $\endgroup$ Oct 1, 2015 at 19:02

1 Answer 1

3
$\begingroup$

This problem is posed and solved in Ahlswede and Katona, Contributions to the geometry of Hamming spaces, page 10. If the number of vectors $N$ is even, the best solution is to choose $N/2$ pairs of a vector and its complement (obtained by switching 0s and 1s). If $N$ is odd then choose $N/2$ such pairs and add an arbitrary vector.

Curiously enough, if you want to minimize the average distance, then the answer is still unknown, though it is suspected to be a Hamming ball.

$\endgroup$
1
  • $\begingroup$ This assumes that the OP attempts to maximize the average distance between two vectors. Apparently the OP is after something else. $\endgroup$ Oct 1, 2015 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.