algorithm - All subsets of size k, maximize difference between subsets

Question

Stock algorithms for enumerating all subsets of size k (from a set of size N) (e.g. as described here: generate all subsets of size k from a set) tend to use a "lexicographic" order, in which the leftmost element varies slowest. I've also found an algorithm that minimizes the difference between successive subsets in the enumeration, kinda like a Gray code.

I would like instead at each step to generate a subset which is maximally different from all preceding subsets. (This is not the same as "maximize difference between successive subsets" as in the previous formulation of the question.) For instance, considering 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 base set is large enough that holding _nC_k items in memory is impractical.

Answer 1

在您想要的输出中，从一个子集到下一个子集不同的元素数量给出了序列2,1,2,1,2。我通过从按字典顺序排列的子集列表中选择第一个，然后是最后一个，然后是第二个，然后是最后一个等来获得相同的序列。在每个步骤中，选择顺序中距离最远且尚未被选择的子集。

我没有得到相同的子集序列，只是相同的差异数序列。

我很满意这也适用于其他几个小案例，现在期待反例和反对票。

啊，所以你不想依赖首先构建按字典顺序排列的子集。我最初的想法是让 2 个子集生成器同时运行，一个从第一个子集 ( eg AB ) 开始并向前运行，另一个从最后一个子集 ( eg CD ) 开始并向后运行。如果你明白我的意思。