3
$\begingroup$

I'm looking for an algorithm that generates all k-combinations of a set, such that each successive combination generated differs as much as possible (or in practice, a lot) from all previous combinations.

For example, given the set {1,2,3,4,5,6}, I might get something like the following:

    {1, 2, 3}
    {4, 5, 6}
    {1, 2, 4}
    {3, 5, 6}
    {1, 4, 6}
    {2, 3, 5}
    {1, 4, 5}
    {2, 3, 6}
    {1, 5, 6}
    {2, 3, 4}
    {1, 2, 5}
    {3, 4, 6}
    {1, 2, 6}
    {3, 4, 5}
    {1, 3, 6}
    {2, 4, 5}
    {1, 3, 5}
    {2, 4, 6}
    {1, 3, 4}
    {2, 5, 6}

I'm aware that using Gray codes would effectively give me the opposite of what I want... unfortunately, it's not obvious to me how I would be able to reverse the Gray code algorithm to produce something similar to my desired output.

Is there a known algorithm that would suit my needs?

$\endgroup$
3
  • $\begingroup$ "all k-combinations of a set". Since (n, k) Gray codes is about permutations, can you confirm that you are talking about subset here? "Each successive combination generated differs as much as possible". Can you give a numerical definition of the difference between two combinations? $\endgroup$
    – John L.
    Jan 4, 2019 at 16:26
  • $\begingroup$ When $k = n/2$ (with $n$ being the universe size), try complementing every other set. $\endgroup$ Jan 30, 2020 at 0:53
  • $\begingroup$ A clearer criterion can be the fairness requirement: Any element cannot appear two times more than any other person at any time of generation. $\endgroup$
    – John L.
    Jan 31, 2020 at 4:02

0

Your Answer

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