Python itertools permutations without repetitions

Question

I have a string show the step going in m x n grid like this problem: https://leetcode.com/problems/unique-paths/

step = 'DDRR'

D mean go Down and R mean go to Right I want to show permutations without replacement, and i found the itertools built-in on Python.But it's say:

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.

So that when I using itertools.permutation(step,4), it's contain many replications.

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

I want something like:

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

I found some answer using set(itertools.permutations(step,4)), but because apply set() method, the itertools.permutation() method still calculate all possibilities. Is there anyway to avoid it, or is there any built-in function can do permutation without repetitions in Python?

im getting empty list using `itertools.permutations(step,4)`, maybe you meant `step = list('DDRR')` — zamir, Feb 16 '20 at 18:57
@Daniel I tried combinations, combinations_with_replacement, permutations and product also, but I can't get exactly what I want — T P, Feb 16 '20 at 19:11
My suspicion is that any algorithm to calculate the permutations wihout repetition will be no more efficient (maybe less efficient) than the itertools and set method you mention in your question, so probably not worth worrying over unless you are going to be using much longer strings. — Simon Notley, Feb 16 '20 at 19:25
@SimonN How "much longer"? For `DDDDDRRRRR` there are already 3.6 million permutations but only 252 different ones, so a reasonable method producing only the latter shouldn't have trouble being faster. — Kelly Bundy, Feb 16 '20 at 19:42
So you want to compute the number of distinct combinations of arranging exactly (m-1) `D` symbols and (n-1) `R`, or equivalently n `R` symbols with (m-1) bars `|` between them. (You don't need to compute the actual combinations, and for m,n up to 100 that would be prohibitive). The number of ways is given by the well-known [Stars-and-Bars formula](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)) — smci, Feb 16 '20 at 19:53
@SimonN: that's totally incorrect, remember that C(n,k) is of the order of O(2^n), so you will blow out memory and CPU very quickly for non-toy values of n. [Remember the identity that [sum(C(n,k)) over k] = 2^n] — smci, Feb 16 '20 at 20:09
@smci yeah, that exactly what I want, but I want to know the way that we can do it easily (in coding) because I think it's a common problem. — T P, Feb 16 '20 at 21:31
Does this answer your question? [permutations with unique values](https://stackoverflow.com/questions/6284396/permutations-with-unique-values) — Joseph Wood, Feb 18 '20 at 22:45

Chris Charley · Accepted Answer · 2020-02-16T23:29:52.003

To get the answer you need, you could use 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']]

To get just the total number, use factorial of number of items divided by the product of factorials for the count of each unique item. Here there are 2 D's and 2 R's

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

score 3 · Answer 2 · answered Feb 16 '20 at 19:20

3

It's a terribly inefficient solution anyway. Just compute the number directly:

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

answered Feb 16 '20 at 19:20

Kelly Bundy

23,480
7
29
65

2

Note that `math.comb` is only available in Python 3.8+. – blhsing Feb 16 '20 at 19:26
@blhsing Yes, and LeetCode runs 3.8.1. – Kelly Bundy Feb 16 '20 at 19:27

blhsing · Answer 3 · 2020-02-16T19:47:53.923

The leetcode problem only asks about the number of unique paths, not a list of unique paths, so to calculate the number you only need to use the combination formula of C(n, k) = n! / (k! x (n - k)!) to find the number of positions where Ds (or Rs) can be placed out of all positions:

from math import factorial

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

so that f(3, 2) returns: 3

and that f(7, 3) returns: 28

On the other hand, if you're interested in producing a list of unique paths, you can use itertools.combinations to do the same as above; that is, to find the positions where Ds (or Rs) can be placed out of all positions:

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))

so that:

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

outputs:

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

score -2 · Answer 4 · answered Feb 16 '20 at 18:58

-2

Try using itertools.combinationss(step,4) instead of itertools.permutations(step,4)

answered Feb 16 '20 at 18:58

Anchal Gupta

219
1
9

1

itertools.combinationss(step,4) will return only ('D', 'D', 'R', 'R') – T P Feb 16 '20 at 18:59
use this then, itertools.combinations_with_replacement(step,4) – Anchal Gupta Feb 16 '20 at 19:01
1

I tried combinations, combinations_with_replacement, permutations and product also, but I can't get exactly what I want – T P Feb 16 '20 at 19:06
No. `itertools.permutations` enumerates all the permutations (with tons of duplicates), but it's overkill. – smci Feb 16 '20 at 20:02

Python itertools permutations without repetitions

4 Answers4

Linked