获取长度为n的所有（n-选择-k）组合

Question

如何从数字列表中获取长度为

n

的所有组合（按顺序）？例如，给定列表

[1, 2, 3, 4]

，并设置

n = 3

，我怎样才能得到这些结果？

[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

---

_{有关所有可能长度的组合，请参阅获取任意长度的列表元素的所有可能 (2^N) 组合。请注意，这不只是迭代可能的长度并组合结果的问题，因为还有其他合理的方法来解决该问题。}

_{要避免输入具有重复元素时出现重复输出，请参阅不带重复的Python组合。}

_{还相关：生成长度为 n 且设置了 k 位的所有二进制字符串}

Answer 1

itertools

可以这样做：

import itertools

for comb in itertools.combinations([1, 2, 3, 4], 3):
    print(comb)

输出：

(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)

Answer 2

添加递归函数：

def combinations(array, tuple_length, prev_array=[]):
    if len(prev_array) == tuple_length:
        return [prev_array]
    combs = []
    for i, val in enumerate(array):
        prev_array_extended = prev_array.copy()
        prev_array_extended.append(val)
        combs += combinations(array[i+1:], tuple_length, prev_array_extended)
    return combs

combinations([1, 2, 3, 4], 3)

输出：

[[1, 2, 3], 
[1, 2, 4], 
[1, 3, 4], 
[2, 3, 4]]

Answer 3

如果您不想一次计算所有组合，您可以制作一个返回长度为 n 的组合的生成器，如下所示：

def combinations(list_get_comb, length_combination):
    """ Generator to get all the combinations of some length of the elements of a list.

    :param list_get_comb: List from which it is wanted to get the combination of its elements.
    :param length_combination: Length of the combinations of the elements of list_get_comb.
    :return: Generator with the combinations of this list.
    """

    # Generator to get the combinations of the indices of the list
    def get_indices_combinations(sub_list_indices, max_index):
        """ Generator that returns the combinations of the indices

        :param sub_list_indices: Sub-list from which to generate ALL the possible combinations.
        :param max_index: Maximum index.
        :return:
        """
        if len(sub_list_indices) == 1:  # Last index of the list of indices
            for index in range(sub_list_indices[0], max_index + 1):
                yield [index]
        elif all([sub_list_indices[-i - 1] == max_index - i for i in
                  range(len(sub_list_indices))]):  # The current sublist has reached the end
            yield sub_list_indices
        else:
            for comb in get_indices_combinations(sub_list_indices[1:],
                                                 max_index):  # Get all the possible combinations of the sublist sub_list_indices[1:]
                yield [sub_list_indices[0]] + comb
            # Advance one position and check all possible combinations
            new_sub_list = []
            new_sub_list.extend([sub_list_indices[0] + i + 1 for i in range(len(sub_list_indices))])
            for new_comb in get_indices_combinations(new_sub_list, max_index):
                yield new_comb  # Return all the possible combinations of the new list

    # Start the algorithm:
    sub_list_indices = list(range(length_combination))
    for list_indices in get_indices_combinations(sub_list_indices, len(list_get_comb) - 1):
        yield [list_get_comb[i] for i in list_indices]

致电：

comb = combinations([1, 2, 3, 4], 3) 

您可以通过调用

next(comb)

或在循环中使用生成器来一一计算长度为 3 的每种可能的组合：

for c in comb:

。

此代码的优点是，如果列表很长，有多种可能的组合，并且您想要获得满足某些条件的所有可能组合之一，则不需要计算所有可能的组合然后按照该标准过滤它们。您可以逐一生成它们，直到找到满足您标准的组合。这将在计算上更加有效。另请注意，上面的代码仅计算长度为 n 的那些组合，而不是计算所有可能的组合，然后按长度过滤它们，这也使其更加高效。

但是，如果需要，您可以通过列出它们来一次计算所有组合

list(comb)

。

Answer 4

此解决方案允许仅选择列表或元素数量介于用户定义的最小值和最大值之间的幂集的子集。每个子集中的元素保持其原始顺序。要获得特定长度 n 的组合，请将元素的最小和最大数量设置为所需值 n。

    def custom_power_set(s, min_cardinal=0, max_cardinal=None):
        """
        Returns a list of all subsets of a list or a set s 
        where the number of elements is between min_cardinal 
        and max_cardinal.
        """
        # Sets max_cardinal to cardinal of set s by default:
        if max_cardinal is None:
            max_cardinal = len(s)
    
        # In case s is a proper set:
        if type(s) == set:
            s = list(s)
    
        out = [[s[i] for i in range(len(s)) if (1 << i & j)]
               for j in range(1 << len(s))
               # condition re number of elements:
               if bin(j).count('1') in range(min_cardinal, max_cardinal + 1)]
    
        return out

示例：

    custom_power_set(range(4), 3, 3)

产生

[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]

作为输出

Answer 5

添加出色的答案，如果您想在实际开始使用组合之前了解组合的数量。如果您的代码动态生成 n 和 k 的值，这可能会有所帮助，这可能会给您带来太多需要处理的组合，或者如果您想要估计运行时间、动态管理资源等等。

例如 (400-choose-22) = 869220235645633221187116908079236800。这可能有点多，您可能希望以与 (4-choose-2) 不同的方式处理这种情况。

要计算金额，最好的方法是使用数学模块的comb功能：

>>> import math
>>> n = 400
>>> k = 22
>>> math.comb(n,k)
869220235645633221187116908079236800
# let's not start calculations that won't finish before the sun blows up

使用此方法而不是以下简单方法的原因：

>>> math.factorial(n)/math.factorial(k)*math.factorial(n-k)
# ...
OverflowError: integer division result too large for a float

前者使用与手动计算相同的阶乘缩减。因此，虽然简单的方法已经无法报告 (400-choose-22) 的数量，但 math.comb(n,k) 的计算速度非常快，直到达到整数字符串转换给出的限制。此限制可以

更改，但对于非常大的 n 和 k 值，检查 min(n/(n-k), n/k) 是否足够接近 1 作为您想要的组合数量可能更合理你的程序要处理。