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?

  • $\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 '19 at 16:26
  • $\begingroup$ When $k = n/2$ (with $n$ being the universe size), try complementing every other set. $\endgroup$ – Yuval Filmus Jan 30 '20 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 '20 at 4:02

if you have a set that has n elements, you can dedicate the numbers from 0 to $2^n-1$ to your set in binary form.for example if you have a set consists of 3 elements,you have the numbers $$000,001,010,011,100,101,110,111$$ that these are the numbers 0 to $2^n-1$ in binary form.then dedicate each digit in a number to the K'th element in your set.for example if the number is 011 and your set consists of {1,2,3},then in this combination you have the subset:{2,3}. now if you want to have max-differing order in your combination,you can use n bit gray code if you have n elements in the set and generate all the combinations by dedicating each digit of a gray code to an element respectively like the binary form I had show above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.