时间戳

首页 > 解决方案 > 来自 2 个列表的所有排列，但以元素数量为条件

python - 来自 2 个列表的所有排列，但以元素数量为条件

问题描述

在 Python 中，我有：

a = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
b = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

我正在尝试构建从 lista或中选择的 10 个这些字符的所有可能排列b，这将包括包含以下内容的任何排列： 至少3 个元素来自a和至少3 个元素来自b。元素可以重复，因为它们是从列表中选择的。

例如，有效排列：wa85ff3d56, 333aaaaaaa,a33333aa33

这样做的最pythonic，最有效的方法是什么？

PS：是的，我知道，答案会非常大。这是预期的。它不会存储在内存中，而是流式传输并用于实时计算。

现在，我生成所有可能的组合，然后排列它们。但是，计算肯定需要几个月的时间。我有这段代码，它可以解决问题，但它显然不是最有效的方法。例如 3 from lista和 7 from list b，它会生成2.864429568e+14排列。所以考虑到我必须这样做 5 次(3,7), (4,6), (5,5), (6,4), (7,3)，我会得到总共1.432214784e+15排列。相比之下，如果没有限制，就会有36^10 = 3.65615844e+15. 因此，这种方法将消除几乎一半的可能排列。

import string
import itertools


a = list(string.digits)
b = list(string.ascii_lowercase)

a_combinaisons_3 = list(itertools.combinations(a, 3))
b_combinaisons_7 = list(itertools.combinations(b, 7))

a3b7_combinaisons = []

for a_element in a_combinaisons_3:
    for b_element in b_combinaisons_7:
        a3b7_combinaisons.append(a_element + b_element)

a3b7_permutations = list(itertools.permutations(a3b7_combinaisons))
print(len(a3b7_combinaisons))  # 78936000
print(len(a3b7_permutations))  # 1.432214784e+15

标签： pythonpermutation

解决方案

我想在这里尝试写一个通用的答案，希望将来有一个很好的规范目标来解决重复的问题。

Python中的组合基础与itertools

重新排序和更换（重复）

了解各种组合迭代器是itertools如何工作的以及它们之间的区别是很重要的。

让我们考虑一个简单的候选集A = [1, 2, 3, 4]，我们想从中绘制三个元素的“组合”（提问者通常会这样说）。

>>> A = [1,2,3,4]

itertools.combinations选择不重新排序（即，每个输出值将按照与输入相同的顺序出现）并且不重复结果值。因此，这仅产生 4 个结果：

>>> list(itertools.combinations(A, 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

itertools.permutations意味着结果可以以任何顺序出现，即输入的给定子集将以不同的顺序出现在输出中多次。

>>> list(itertools.permutations(A, 3)) # 24 results omitted for brevity

这四个combinations以六个顺序出现，总共有 24 个结果。

itertools.combinations_with_replacement选择不重新排序，但允许多次选择输入中的元素：

>>> list(itertools.combinations_with_replacement(A, 3)) # 20 results omitted for brevity

有四个结果，其中每个元素被选择了 3 次，6 个在双精度后跟一个单音（必须更高），六个在单音后跟一个双精度，再加combinations上所有单曲中的四个。在一般情况下计算结果并不容易。

如果您想在输出结果中允许重复和重新排序，您可以使用itertools.product：

>>> list(itertools.product(A, repeat=3)) # 64 results omitted for brevity

简单地说，每三次我们从四个元素中自由选择，得到 4 * 4 * 4 = 64 个结果。

itertools.product实现了所谓的笛卡尔积。通常，它从多个指定序列中分别提取一个元素。但是生成“置换置换”与多次从同一序列中拉出一个元素是一回事，因此repeat提供了关键字作为此操作的便捷快捷方式 - 因此您不必多次指定序列。我的意思是，你可以写itertools.product(*[A]*3)，但这很难看。

候选集中的重复怎么办？

这与 OP 的问题无关；但为了完整起见，重要的是要理解这些函数都不关心候选集的元素是否相等，甚至相同：

>>> x = object()
>>> candidates = [x, x, x, x]
>>> results = list(itertools.combinations(candidates, 3))
>>> len(results)
4
>>> results[0] == results[1] == results[2] == results[3]
True

我们如何实现约束？

最简单的方法是生成一个包容性结果（在 OP 的情况下，通过将a和b候选者连接在一起，并生成其中product的 10 个）并过滤掉不符合要求的事物。但是，这效率低下并且可能很难看（我们需要分析输出元组以确定其元素是否满足条件 - 在 OP 的情况下，它们是来自a还是来自b。如果您确实想采用这样的方法，我通常建议编写一个生成器函数：

def OP_problem():
    for result in itertools.product(a+b, repeat=10):
        a_count = len(x for x in result if x in a)
        # the trick is that every element was either from a or b;
        # so "at least 3 a's and at least 3 b's" is equivalent to
        # "at least 3 a's and at most 7 a's".
        if 3 <= a_count <= 7:
            yield result

或者在足够简单的情况下，生成器表达式：

(
    # maybe you don't think this is simple enough :)
    result for result in itertools.product(a+b, repeat=10)
    if 3 <= len(x for x in result if x in a) <= 7
)

通常最好尝试将问题分解成更小的部分并将结果放在一起。例如，该文档有一个计算能力集的配方，它简单地将 0 个元素、1 个元素等组合的结果链接到所有元素。（另一种方法是找到 N 个布尔值的笛卡尔积，每个布尔值表示是否包含给定元素，然后将它们转换为子集。）

在我们的例子中，我们可以分别找到每个a元素计数的结果。让我们考虑每个列表中有 5 个元素的情况；应该清楚如何概括并组合结果（提示：使用itertools.chain.from_iterable，如powerset文档中的配方所示）。

疑难案例：分区和选位

我想在这里展示一种先进的技术，以解决从中选择 5 个元素a和从中选择 5 个元素b并将它们混合的问题。这个想法很简单，我们从所有可能的位置（即，索引到 10 个元素的序列中）中选择a 将去的位置，并为每个位置生成相应的输出结果。这些位置是没有替换的组合（你明白为什么吗？）可能的索引值。

因此，类似：

def make_combination(letter_positions, chosen_letters, chosen_digits):
    result = [None] * 10
    for letter, position in zip(chosen_letters, letter_positions):
        result[position] = letter
    # Figure out where the digits go, using set arithmetic to find the
    # remaining positions, then putting them back in ascending order.
    digit_positions = sorted(set(range(10)) - set(chosen_letters))
    for digit, position in zip(chosen_digits, digit_positions):
        result[position] = digit
    assert None not in result
    return tuple(result)


def five_letters_and_five_digits():
    letters = 'abcdefghijklmnopqrstuvwxyz'
    digits = '0123456789'
    # It's not *easy*, but it's fairly elegant.
    # We separately generate the letter positions, letter selection
    # and digit selection, using `product` to get the cartesian product
    # of *those* possibilities; then for each of those, we translate
    # into a desired output - using `starmap` to iterate.
    return itertools.starmap(
        make_combination, 
        itertools.product(
            itertools.combinations(range(10), 5),
            itertools.product(letters, repeat=5),
            itertools.product(digits, repeat=5)
        )
    )

选择位置的技术对于解决分区问题也很有用。这个想法很简单，您选择分区所在的位置（对于 N 个元素，通常会有 N-1 个位置放置它们），作为组合 - 可以使用（如果允许零大小分区）或不使用（否则）替换。

推荐阅读