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
– zamir, Commented Feb 16, 2020 at 18:57
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
– Simon Notley, Commented Feb 16, 2020 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
– Kelly Bundy, Commented Feb 16, 2020 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 — smci
– smci, Commented Feb 16, 2020 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
– smci, Commented Feb 16, 2020 at 20:09

Chris Charley · Accepted Answer · 2020-02-16 23:29:52Z

6

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

edited Feb 16, 2020 at 23:29

answered Feb 16, 2020 at 19:55

Chris Charley

6,6972 gold badges27 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kelly Bundy · Accepted Answer · 2020-02-16 19:20:11Z

3

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

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

answered Feb 16, 2020 at 19:20

Kelly Bundy

28k7 gold badges34 silver badges76 bronze badges

2 Comments

blhsing Over a year ago

Note that math.comb is only available in Python 3.8+.

Kelly Bundy Over a year ago

@blhsing Yes, and LeetCode runs 3.8.1.

blhsing · Accepted Answer · 2020-02-16 19:47:53Z

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

Anchal Gupta · Accepted Answer · 2020-02-16 18:58:35Z

-2

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

answered Feb 16, 2020 at 18:58

Anchal Gupta

3371 silver badge9 bronze badges

4 Comments

T P Over a year ago

itertools.combinationss(step,4) will return only ('D', 'D', 'R', 'R')

Anchal Gupta Over a year ago

use this then, itertools.combinations_with_replacement(step,4)

T P Over a year ago

I tried combinations, combinations_with_replacement, permutations and product also, but I can't get exactly what I want

smci Over a year ago

No. itertools.permutations enumerates all the permutations (with tons of duplicates), but it's overkill.

Collectives™ on Stack Overflow

Python itertools permutations without repetitions

4 Answers 4

Comments

2 Comments

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related