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

与one-liner:

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

您的问题是关于寻找 permutations of multisets。 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)

Python 更有效的排列

Python More efficient permutation

python

python-3.x

list

permutation

combinatorics