Python更有效的排列

Question

我有一个字符串，它由x个字母'r'和y个字母'u'组成。我的目标是打印出相同数量的x和y的所有可能组合以不同的顺序。这是我的工作代码示例。

import itertools
RIGHT = 'r'
UP = 'u'
def up_and_right(n, k, lst):
case = RIGHT*n + UP*k
return [''.join(p) for p in set(itertools.permutations(case))]

输入输出示例:

input:
lst1 = []
up_and_right(2,2,lst1)
lst1 => output:['ruru', 'urur', 'rruu', 'uurr', 'urru', 'ruur']

我的问题是，当输入是一个大于10的整数时，代码需要一分钟来计算。如何提高计算时间?提前感谢!

Answer 1

尝试itertools.combinations:

import itertools
RIGHT = "r"
UP = "u"

def up_and_right(n, k):
out = []
for right_idxs in itertools.combinations(range(n + k), r=n):
s = ""
for idx in range(n + k):
if idx in right_idxs:
s += RIGHT
else:
s += UP
out.append(s)
return out

print(up_and_right(2, 2))

打印:

['rruu', 'ruru', 'ruur', 'urru', 'urur', 'uurr']

一行程序

---

:

def up_and_right(n, k):
return [
"".join(RIGHT if idx in right_idxs else UP for idx in range(n + k))
for right_idxs in itertools.combinations(range(n + k), r=n)
]

Answer 2

你的问题是关于找到多集的排列。sympy有一个处理它的实用方法。

from sympy.utilities.iterables import multiset_permutations
def up_and_right2(n,k):
case = RIGHT*n + UP*k
return list(map(''.join, multiset_permutations(case)))

测试:

y = up_and_right(n,k)
x = up_and_right2(n,k)
assert len(x) == len(y) and set(y) == set(x)

时间:

n = 5
k = 6
%timeit up_and_right(n,k)
3.57 s ± 52.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit up_and_right2(n,k)
4.17 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)