Python перестановок itertools без повторов - PullRequest
Новая
       131

Python перестановок itertools без повторов

1 голос
/ 16 февраля 2020

У меня есть строка, показывающая шаг в сетке mxn, подобный этой задаче: https://leetcode.com/problems/unique-paths/

step = 'DDRR'

D означает go Вниз и R означает go вправо Я хочу показать перестановки без замены, и я обнаружил, что встроенные средства itertools Python. Но говорят:

Элементы обрабатываются как уникальные в зависимости от их положения, а не от их значения. Поэтому, если входные элементы уникальны, повторных значений не будет.

Так что, когда я использую itertools.permutation (шаг 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?

Ответы [ 4 ]

2 голосов
/ 16 февраля 2020

Чтобы получить нужный ответ, вы можете использовать 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
2 голосов
/ 16 февраля 2020

Задача leetcode касается только количества уникальных путей, а не списка уникальных путей, поэтому для вычисления числа вам нужно использовать формулу комбинации C(n, k) = n! / (k! x (n - k)!), чтобы найти количество позиций, где D s (или R s) могут быть размещены из всех позиций: 

from math import factorial

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

, так что f(3, 2) возвращает: 3

, а f(7, 3) возвращает: 28

С другой стороны, если вы заинтересованы в создании списка уникальных путей, вы можете использовать itertools.combinations, чтобы сделать то же самое, что и выше; то есть, чтобы найти позиции, в которых D с (или R с) могут быть размещены из всех позиций: 

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
2 голосов
/ 16 февраля 2020

Это ужасно неэффективное решение в любом случае. Просто вычислите число напрямую: 

math.comb(m + n - 2, m - 1)
0 голосов
/ 16 февраля 2020

Попробуйте использовать itertools.combinationss (шаг 4) вместо itertools.permutations (шаг 4)

...