从整数列表生成 k-set 的最快方法是什么？

Question

我想生成所有 k 集（k=2 到 4），它始终包含整数有序列表 {0, 1, 2, 3} 中的第一个元素 0： [{0,1},{0,2},{0,3},{0,1,2},{0,1,3},{0,2,3},{0,1,2, 3}].

目前我的方法是 * m=2: [{0,1},{0,2},{0,3}], * m=3：从 m=2 派生，仅在列表中添加大于 (m-1) 集合中最大元素的元素：[{0,1,2}, {0,1,3}, { 0,2,3}}]，例如，这里 [2,3] 比集合 {0,1} 中的最大整数 1 大，所以它们被添加并且我得到了另外 2 个集合 {0,1 ,2},{0,1,3}.

它可以工作，但是当 n 很大时它不够快。

我想知道生成这些集合的更快方法是什么。

Answer 1

不要在意 0 - 最后添加它

使用从 1 到 2^(k-1) - 1 的计数器进行简单循环（此处为 1..7）

每个计数器值对应一组元素 - 考虑如果第 j 位为 1，则 j 出现在集合中。

例如5=二进制101对应集合{1,3}（第一位和第三位为1）

Answer 2

如果k固定为2-4但n变化，则没有理由避免使用嵌套循环。这是一个 Python 生成器，它将有效地迭代所有这些子集。它大量使用内置函数 enumerate() 但核心思想很容易用任何语言实现：

def enumerator(nums):
    #enumerates the k-element subsets of set nums
    #which have between 2 and 4 elements, including
    #the smallest element:

    pool = sorted(list(nums)) #make a sorted copy
    a = pool[0]
    pool = pool[1:] #remaining items
    n = len(pool)

    #first the 2-element subsets:

    for b in pool:
        yield {a,b}

    #3-element subsets:
    for i,b in enumerate(pool[:n-1]):
        for c in pool[i+1:]:
            yield {a,b,c}

    #4-element subsets:

    for i,b in enumerate(pool[:n-2]):
        for j,c in enumerate(pool[i+1:n-1]):
            for d in pool[j+2:]:  #enumerate() starts with 0 - so bump up 2
                yield {a,b,c,d}

例如：

>>> for s in enumerator({0,1,2,3}): print(s)

{0, 1}
{0, 2}
{0, 3}
{0, 1, 2}
{0, 1, 3}
{0, 2, 3}
{0, 1, 2, 3}

如果 k 未固定在此范围内，请使用 combinations 上维基百科文章中描述的算法之一。

从整数列表生成 k-set 的最快方法是什么？

What's the fastest way to generate k-set from a list of integers?

algorithm

set

combinatorics