所有大小为k的子集，最大化子集之间的差异

Question

4

股票算法用于枚举所有大小为k的子集（从大小为N的集合中）（例如，如此描述：generate all subsets of size k from a set）以使用“字典顺序”，其中最左边的元素变化最慢。我还发现了一种算法，可以使枚举中连续子集之间的差异最小，有点像格雷码。

相反，我希望在每一步中生成一个与所有先前的子集最不同的子集。（这与先前的问题陈述中的“最大化连续子集之间的差异”不同。）例如，考虑从大小为8的集合中选择4个元素的子集，一种可接受的排序方式开始

ABCD
    EFGH
AB    GH
  CDEF
AB  EF
  CD  GH

请注意，基础集合足够大，以至于在内存中保存_nC_k个项目是不切实际的。

- zwol

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- High Performance Mark · Accepted Answer

在您所期望的输出中，每个子集之间不同元素的数量给出了序列 2,1,2,1,2。我通过从按字典顺序排序的子集列表中选择第一个、最后一个、第二个、第二个最后等方式来获得相同的序列。在每一步中，选择在顺序中最远且尚未被选择的子集。

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

我已经满足于此对于其他一些小情况也适用，并且现在期待反例和负票。

啊，所以您不想依赖于首先构建按字典顺序排列的子集集合。我的初始想法是同时运行两个子集生成器，一个从第一个子集（例如AB）开始向前，另一个从最后一个（例如CD）开始向后。如果您明白我的意思。