获取长度为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个二进制位的字符串}

- user3685412

---

如果有 [1,2,3] 表示你不想要 [2,1,3]，那么你所描述的是“组合”，而不是“排列”。 - jwodder

有点类似，但并不完全相同。在我的情况下，如果我已经有了[1,2,3]，那么[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]和[3,2,1]对我来说是没有用的。@jwodder 对不起，我不知道其中的区别。:S - user3685412

我还没有找到这个问题的确切副本，其中OP想要特定长度的所有组合。我能找到的其他组合问题都要求生成完整的幂集，有趣的是。在找到这样的问题之前（可能存在），我会说这不是一个重复的问题。 - jpmc26

@J.F.Sebastian 我强烈不同意那是一个重复的问题。那个问题施加了使用递归的额外限制，而这里的答案并没有出现在那个问题中。 - jpmc26

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)

- jlb83

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]]

- RoyR

---

到目前为止，这是我发现的最易读、最干净、最优雅的解决方案。赞！这个答案应该排名更高。 - Luca Gibelli

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)或在循环中使用生成器：for c in comb:，逐个计算长度为3的每个可能组合。

这段代码的优点在于，如果列表非常长，有许多可能的组合，并且您想要获取符合某些条件的所有可能组合之一，您不需要计算所有可能的组合，然后根据该条件过滤它们。您只需一次生成一个组合，直到找到符合条件的组合为止。这将更加高效。此外，请注意，上述代码仅计算长度为n的组合，而不是计算所有可能的组合并然后按长度进行过滤，这也使其更加高效。

但是，如果您想要的话，您可以通过列出它们来一次性计算所有组合：list(comb)。

- IgnacioGaBo

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]] 作为输出

- beatriz de otto