Python itertools 不重复的排列

Question

我有一个字符串显示 mxn 网格中的步骤，就像这个问题： https ://leetcode.com/problems/unique-paths/

step = 'DDRR'

D 表示“向下”，R 表示“向右” 我想显示无需替换的排列，我发现 Python 内置了 itertools。但是它说：

元素根据其位置而不是其值被视为唯一。因此，如果输入元素是唯一的，则不会有重复值。

因此，当我使用 itertools.permutation(step,4) 时，它包含许多重复。

>>> itertools.permutations(step,4)
('D', 'D', 'R', 'R')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'D', 'R', 'R')
('D', 'D', 'R', 'R')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('R', 'D', 'D', 'R')
('R', 'D', 'R', 'D')
('R', 'D', 'D', 'R')
('R', 'D', 'R', 'D')
('R', 'R', 'D', 'D')
('R', 'R', 'D', 'D')
('R', 'D', 'D', 'R')
('R', 'D', 'R', 'D')
('R', 'D', 'D', 'R')
('R', 'D', 'R', 'D')
('R', 'R', 'D', 'D')
('R', 'R', 'D', 'D')

我想要这样的东西：

('R', 'D', 'R', 'D')
('R', 'D', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'D', 'R', 'R')
('D', 'R', 'D', 'R')
('R', 'R', 'D', 'D')

我使用set(itertools.permutations(step,4))找到了一些答案，但因为应用 set() 方法， itertools.permutation() 方法仍然计算所有可能性。有没有办法避免它，或者有没有内置函数可以在 Python 中进行排列而无需重复？

Answer 1

要获得您需要的答案，您可以使用multiset_permutations

>>> from sympy.utilities.iterables import multiset_permutations
>>> from pprint import pprint
>>> pprint(list(multiset_permutations(['D','D','R','R'])))
[['D', 'D', 'R', 'R'],
 ['D', 'R', 'D', 'R'],
 ['D', 'R', 'R', 'D'],
 ['R', 'D', 'D', 'R'],
 ['R', 'D', 'R', 'D'],
 ['R', 'R', 'D', 'D']]

要获得总数，请使用项目数的阶乘除以每个唯一项目的计数阶乘的乘积。这里有 2 个 D 和 2 个 R

>>> from math import factorial
>>> factorial(4)//(factorial(2)*factorial(2))
6