Python itertools 无重复排列

Question

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

step = 'DDRR'

D表示向下，R表示向右我想显示排列而不用替换，我发现 Python.But 上内置了 itertools 说：

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values.

所以当我使用 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

尝试使用 itertools.combinationss(step,4) 而不是 itertools.permutations(step,4)

Answer 2

leetcode问题只问唯一路径的个数，而不是唯一路径的列表，所以计算个数只需要用C(n, k) = n! / (k! x (n - k)!)的组合公式求出位置的个数Ds（或Rs）可以放出所有位置：

from math import factorial

def f(m, n):
    return factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1)

所以 f(3, 2) returns: 3

那 f(7, 3) returns: 28

另一方面，如果您对生成唯一路径列表感兴趣，可以使用 itertools.combinations 来执行与上述相同的操作；即从所有位置中找出可以放置Ds（或Rs）的位置：

from itertools import combinations
def f(m, n):
    for positions in map(set, combinations(range(m + n - 2), m - 1)):
        yield ''.join('DR'[i in positions] for i in range(m + n - 2))

这样：

print(*f(7, 3), sep='\n')

输出：

RRRRRRDD
RRRRRDRD
RRRRRDDR
RRRRDRRD
RRRRDRDR
RRRRDDRR
RRRDRRRD
RRRDRRDR
RRRDRDRR
RRRDDRRR
RRDRRRRD
RRDRRRDR
RRDRRDRR
RRDRDRRR
RRDDRRRR
RDRRRRRD
RDRRRRDR
RDRRRDRR
RDRRDRRR
RDRDRRRR
RDDRRRRR
DRRRRRRD
DRRRRRDR
DRRRRDRR
DRRRDRRR
DRRDRRRR
DRDRRRRR
DDRRRRRR

Answer 3

无论如何，这是一个非常低效的解决方案。直接计算数字即可：

math.comb(m + n - 2, m - 1)

Answer 4

要获得所需的答案，您可以使用 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

Python itertools 无重复排列

Python itertools permutations without repetitions

python

permutation

itertools

combinatorics