# Generation of all k-combinations of a set in max-differing order

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?

• "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? – John L. Jan 4 '19 at 16:26
• When $k = n/2$ (with $n$ being the universe size), try complementing every other set. – Yuval Filmus Jan 30 '20 at 0:53
• A clearer criterion can be the fairness requirement: Any element cannot appear two times more than any other person at any time of generation. – 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.