算法：返回n个元素中选k个的所有组合以及相应的补集列表

Question

这与这个问题有关，但我还想以一种高效的方式使用python或c++来获取相应的补充有序列表，其中包含未选择的元素。例如，对于有序列表list=(0,1,1,2,3,3)，当我们选择3个元素时，一个可能的返回对应为(0,1,3)和(1,2,3)。此外，我希望该函数返回总共C(n,k)个条目，因此在返回结果中，对于(0,1,3)和(1,2,3)这一对，应重复4次。

以下是一个简短输入的完整示例：定义一个函数foo(list,k)，那么foo([0,1,1],1)应返回长度为C(3,1)=3的列表r。

r(0)=[[0],[1,1]] (choose 0, complement list is [1,1])
r(1)=[[1],[0,1]] (choose first 1, complement list is [0,1])
r(2)=[[1],[0,1]] (choose second 1, complement list is [0,1])

- egwene sedai

---

我不确定我理解了，也许可以加上一些例子或解释。例如，"补充排序列表" 到底是什么意思？"当我们选择3个元素时，一个可能的返回值对应该是(0,1,3)和(1,2,3)" 这句话具体是什么意思？ - undefined

根据您的建议，我添加了一个示例。补充列表是一个包含未选择元素的列表。 - undefined

Answer 1

您可以使用基本的组合算法，但有一个例外，它会返回一个元组：其中包含“在”和“不在”元素。然后，只需递归生成其余列表的组合，并将第一个元素添加到“在”或“不在”列表中。

以下是一些Python代码：

def comb_and_comp(lst, n):
    # no combinations
    if len(lst) < n:
        return
    # trivial 'empty' combination
    if n == 0 or lst == []:
        yield [], lst
    else:
        first, rest = lst[0], lst[1:]
        # combinations that contain the first element
        for in_, out in comb_and_comp(rest, n - 1):
            yield [first] + in_, out
        # combinations that do not contain the first element
        for in_, out in comb_and_comp(rest, n):
            yield in_, [first] + out

这将一次性创建“in”和“out”列表，而不是在第二次遍历中创建补集。

- tobias_k

---

这是一种更高效的方法，我认为它可以很好地扩展到非常大的列表。谢谢！ - undefined

Answer 2

好的，那么使用这个算法来生成所有n中k的组合，然后使用该算法获取补集列表。

(假设给出的组合是索引而不是实际值) 对于你的例子，它应该是：

foo([0,1,1],1) // i.e indices are [0,1,2] with values [0,1,1]
r(0)=[[0],[1,2]] (choose 0, complement list is [1,2])
r(1)=[[1],[0,2]] (choose first 1, complement list is [0,2])
r(2)=[[1],[0,1]] (choose second 1, complement list is [0,1])

该算法是（改编自这篇文章）：

def complement(n, k, combination):
    # assume the combination values/indices are given in ascending order (i.e lexicographic)
    complement = []
    i=0 
    j=0 
    while i < n:
        if j >= k or i<combination[j]: complement.append(i)
        else: j+=1
        i+=1
    return complement

- Nikos M.

---

你指的是https://dev59.com/9nVC5IYBdhLWcg3w-mVO中的哪个算法/实现？ - undefined

@moi，哎呀，抱歉我误读了你的评论，并参考了另一个答案。实际上，选择哪个算法并不重要，只要它能生成 k 个元素在 n 个元素中的组合即可。选择适合自己的算法就好，尽管能够生成索引而不仅仅是值是一个要求。 - undefined