如何计算我可以在 python 中订购列表的多少种不同方式

Question

我对如何做到这一点有点困惑，我知道这可能也需要一些概率知识（我缺乏）。

我怎样才能计算出有多少种方式，并得到所有的可能性，我可以用多少种方式订购一个清单？

例如，如果我有lst = ["a", "a", "a", "a", "b", "b", "b"]，我可以订购多少种方式this/how，我可以获得所有可能的组合吗？我一直在寻找 itertools 但没有找到适合它的东西。

Answer 1

您可以使用 permutations() 获取所有排列，并使用 set() 删除重复项：

>>> from itertools import permutations
>>> set(permutations(lst))
{('b', 'a', 'b', 'a', 'a', 'a', 'b'), ('b', 'a', 'a', 'b', 'a', 'a', 'b'), ('b', 'a', 'a', 'b', 'b', 'a', 'a'), ('a', 'a', 'b', 'b', 'a', 'a', 'b'), ('a', 'a', 'b', 'a', 'b', 'b', 'a'), ('b', 'b', 'a', 'b', 'a', 'a', 'a'), ('b', 'a', 'a', 'a', 'b', 'a', 'b'), ('b', 'a', 'b', 'a', 'b', 'a', 'a'), ('b', 'b', 'a', 'a', 'b', 'a', 'a'), ('b', 'b', 'b', 'a', 'a', 'a', 'a'), ('a', 'a', 'a', 'b', 'a', 'b', 'b'), ('a', 'a', 'b', 'b', 'b', 'a', 'a'), ('a', 'a', 'a', 'b', 'b', 'b', 'a'), ('a', 'b', 'b', 'a', 'a', 'b', 'a'), ('b', 'a', 'b', 'b', 'a', 'a', 'a'), ('a', 'b', 'b', 'b', 'a', 'a', 'a'), ('a', 'b', 'a', 'a', 'a', 'b', 'b'), ('a', 'b', 'a', 'b', 'a', 'b', 'a'), ('a', 'b', 'b', 'a', 'a', 'a', 'b'), ('a', 'b', 'b', 'a', 'b', 'a', 'a'), ('a', 'a', 'b', 'a', 'b', 'a', 'b'), ('a', 'b', 'a', 'b', 'b', 'a', 'a'), ('b', 'b', 'a', 'a', 'a', 'b', 'a'), ('a', 'a', 'b', 'a', 'a', 'b', 'b'), ('a', 'a', 'a', 'a', 'b', 'b', 'b'), ('b', 'a', 'b', 'a', 'a', 'b', 'a'), ('b', 'b', 'a', 'a', 'a', 'a', 'b'), ('a', 'b', 'a', 'a', 'b', 'b', 'a'), ('b', 'a', 'a', 'b', 'a', 'b', 'a'), ('a', 'a', 'a', 'b', 'b', 'a', 'b'), ('a', 'b', 'a', 'a', 'b', 'a', 'b'), ('a', 'a', 'b', 'b', 'a', 'b', 'a'), ('a', 'b', 'a', 'b', 'a', 'a', 'b'), ('b', 'a', 'a', 'a', 'a', 'b', 'b'), ('b', 'a', 'a', 'a', 'b', 'b', 'a')}
>>>

请注意，他的方法不是优化方法，因为它首先计算所有排列，虽然它 returns 是一个迭代器并且不会将所有排列都存储在内存中，但这仍然不是最好的方法如果您处理的是非大型数据集，那就很好了。

如果您想使用优化的方式，您可以自定义 permutations 的等效函数，其中 has mentioned in documentation.

Answer 2

正如 Kasramvd 提到的，使用 itertools.permutations 不是生成包含重复元素的列表的排列的有效方法。您的示例数据有 7 个元素，因此 itertools.permutations 生成 7！ = 5040 个排列，但只有 35 = 7 choose 3 个独特的排列。

幸运的是，由于 14 世纪的印度数学家 Narayana Pandita 发明了一种古老的排列算法，它可以按词典顺序生成排列，从而优雅地处理重复的元素。这是一个说明（源自 Wikipedia 文章），展示了该算法如何从当前排列生成下一个排列。

找到最大索引 j 使得 a[j] < a[j + 1]。如果不存在这样的索引，该排列是最后一个排列。
找到大于 j 的最大索引 k，使得 a[j] < a[k]。
将 a[j] 的值与 a[k] 的值交换。
反转从 a[j + 1] 到最后一个元素 a[n] 的序列。

这是一个实现该算法的生成器函数。为了获得所有排列，输入列表必须按字典顺序按升序排序。

def lexico_permute(a):
    a = list(a)
    yield a
    n = len(a) - 1
    while True:
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return

        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break

        a[j], a[k] = a[k], a[j]
        a[j+1:] = a[j+1:][::-1]
        yield a

# Test
lst = ["a", "a", "a", "a", "b", "b", "b"]

for i, u in enumerate(lexico_permute(lst), 1):
    print(i, u)

输出

1 ['a', 'a', 'a', 'a', 'b', 'b', 'b']
2 ['a', 'a', 'a', 'b', 'a', 'b', 'b']
3 ['a', 'a', 'a', 'b', 'b', 'a', 'b']
4 ['a', 'a', 'a', 'b', 'b', 'b', 'a']
5 ['a', 'a', 'b', 'a', 'a', 'b', 'b']
6 ['a', 'a', 'b', 'a', 'b', 'a', 'b']
7 ['a', 'a', 'b', 'a', 'b', 'b', 'a']
8 ['a', 'a', 'b', 'b', 'a', 'a', 'b']
9 ['a', 'a', 'b', 'b', 'a', 'b', 'a']
10 ['a', 'a', 'b', 'b', 'b', 'a', 'a']
11 ['a', 'b', 'a', 'a', 'a', 'b', 'b']
12 ['a', 'b', 'a', 'a', 'b', 'a', 'b']
13 ['a', 'b', 'a', 'a', 'b', 'b', 'a']
14 ['a', 'b', 'a', 'b', 'a', 'a', 'b']
15 ['a', 'b', 'a', 'b', 'a', 'b', 'a']
16 ['a', 'b', 'a', 'b', 'b', 'a', 'a']
17 ['a', 'b', 'b', 'a', 'a', 'a', 'b']
18 ['a', 'b', 'b', 'a', 'a', 'b', 'a']
19 ['a', 'b', 'b', 'a', 'b', 'a', 'a']
20 ['a', 'b', 'b', 'b', 'a', 'a', 'a']
21 ['b', 'a', 'a', 'a', 'a', 'b', 'b']
22 ['b', 'a', 'a', 'a', 'b', 'a', 'b']
23 ['b', 'a', 'a', 'a', 'b', 'b', 'a']
24 ['b', 'a', 'a', 'b', 'a', 'a', 'b']
25 ['b', 'a', 'a', 'b', 'a', 'b', 'a']
26 ['b', 'a', 'a', 'b', 'b', 'a', 'a']
27 ['b', 'a', 'b', 'a', 'a', 'a', 'b']
28 ['b', 'a', 'b', 'a', 'a', 'b', 'a']
29 ['b', 'a', 'b', 'a', 'b', 'a', 'a']
30 ['b', 'a', 'b', 'b', 'a', 'a', 'a']
31 ['b', 'b', 'a', 'a', 'a', 'a', 'b']
32 ['b', 'b', 'a', 'a', 'a', 'b', 'a']
33 ['b', 'b', 'a', 'a', 'b', 'a', 'a']
34 ['b', 'b', 'a', 'b', 'a', 'a', 'a']
35 ['b', 'b', 'b', 'a', 'a', 'a', 'a']

FWIW，对于问题中给出的列表，此代码比使用 set(permutations(lst)) 快约 8 倍；对于更大的输入列表，可以节省更多时间。

lexico_permute 最初从输入序列（也可以是元组、字符串等）创建一个新列表。然后生成新列表，就地推进到下一个排列，并再次生成相同的列表。等等。因此，如果您只是将其输出附加到一个空列表，您最终会得到一个列表列表，该列表仅包含对同一列表的多个引用。这通常不是很有用。 :)

解决这个问题的简单方法是附加一份 lexico_permute 生成的列表副本，例如

all_perms = []
for u in lexico_permute(lst):
    all_perms.append(u[:])

或作为列表理解：

all_perms = [u[:] for u in lexico_permute(lst)]

或者，将 lexico_permute 中的两个 yield 语句更改为

yield a[:]

然后你可以做

all_perms = list(lexico_permute(lst))

Answer 3

听起来您只是在尝试计算可区分排列的数量，而不是生成它们。

如果你有 n₁ 种不可区分的元素，n₂ 种不可区分的元素，最多 n_k 最后一类元素，那么你的集合不可区分排列数的公式是：

要在 Python 中进行计算，我们可以这样做：

from collections import Counter
from math import factorial
from functools import reduce
import operator    


def unique_permutations(lst):
    c = Counter(lst)
    return factorial(len(lst)) // reduce(operator.mul, map(factorial, c.values()))

这是输出：

>>> unique_permutations(["a", "a", "a", "a", "b", "b", "b"])
35

如何计算我可以在 python 中订购列表的多少种不同方式

How to calculate how many different ways I can order a list in python

python

probability