获取所有长度为 n 的 (n-choose-k) 组合

问题描述：

n如何从数字列表中获取所有长度组合（按顺序） ？例如，给定列表[1, 2, 3, 4]和设置n = 3，如何获得这些结果？

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

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

为了避免输入有重复元素时出现重复输出，请参阅无重复的 Python 组合。

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

解决方案 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)

解决方案 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]]

解决方案 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)。

解决方案 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]]输出

解决方案 5：

除了出色的答案之外，如果您希望在实际开始处理组合之前了解组合的数量，这可能会有所帮助。如果您的代码动态地产生n和k 的值，这可能会给您太多的组合而无法处理，或者如果您想估计运行时间、动态管理资源等，这可能会有所帮助。

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

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

>>> 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/(nk), n/k) 是否足够接近 1 以成为您希望程序处理的组合数量可能更合理。