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

Question

我对如何做到这一点有点困惑,我知道它可能也需要一点概率知识(我缺乏).

我如何计算有多少种方式,并且还可以获得我可以订购列表的方式的所有可能性？

例如,如果我有lst = ["a", "a", "a", "a", "b", "b", "b"],我可以订购多少种方式/如何获得所有可能的组合？我一直在寻找,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')}
>>> 

请注意,他的方法不是一种优化的方法,因为它首先计算所有排列,虽然它返回一个迭代器并且不会将所有排列存储在内存中但是它仍然不是最好的方式,如果你正在处理非大数据集.

如果要使用优化方法,可以自定义文档中提到permutations的等效函数.

Answer 2

如Kasramvd提及,使用itertools.permutations是不生成包含重复单元的明细表的排列的有效方式.您的示例数据有7个元素,因此itertools.permutations生成7个!= 5040个排列,但只有35 = 7选择3个独特的排列.

幸运的是,有一种古老的排列算法,由于14世纪的印度数学家Narayana Pandita,它以字典顺序产生排列,可以优雅地处理重复元素.这是一个描述(来自维基百科的文章),显示了该算法如何从当前的算法生成下一个排列.

1. 找到最大的索引j,使得a [j] <a [j + 1].如果不存在这样的索引,则排列是最后的排列.
2. 找到大于j的最大索引k,使得a [j] <a [k].
3. 将a [j]的值与[k]的值交换.
4. 将序列从[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)]

或者,将两个yield语句更改lexico_permute为

yield a[:]

然后你就可以做到

all_perms = list(lexico_permute(lst))