All subsets of size k maximize the difference between the subsets

Question

Stock algorithms for listing all subsets of size k (from a set of size N) (for example, as described here: generate all subsets of size k from a set ) tend to use a “lexicographic” order in which the left-most element changes more slowly. I also found an algorithm that minimizes the difference between consecutive subsets in an enum, like Gray code .

Instead, I would like to generate at each step a subset that is as different as possible from all previous subsets. (This is not the same as "maximizing the difference between consecutive subsets" as in the previous question statement). For example, looking at subsets of size 4 from a set of size 8, one acceptable order begins

ABCD EFGH AB GH CDEF AB EF CD GH 

Note that the basic set is large enough that holding _n C _k elements in memory is impractical.

Answer 1

In the desired conclusion, the number of elements that differ from one subset to the next gives the sequence 2,1,2,1,2 . I get the same sequence, choosing from the lexicographically ordered list of subsets the first, then the last, then the second, then the second last, etc. At each step, select the subset that is farthest in order and which has not yet been selected.

I do not get the same sequence of subsets, exactly the same sequence of numbers of differences.

I have satisfied myself that this also works for several other small cases, and now I look forward to counter examples and voices.

Ahh, so you do not want to rely on creating a lexicographically ordered set of subsets first. My initial thought is that 2 subset generators are running at the same time, one of which starts from the first subset (like AB ) and jumps forward, and the second starts from the last (like CD ) and goes back. If you understand what I mean.