Efficiently finding all possible unique permutations of a word

Question

Lets say I have the following word : "aabb" then all possible unique permutations are : "aabb","abab","baba","abba","baab" and "bbaa". Notice that that there are not 4! = 24 ways to do so but 4 choose 2 = 6. What I currently have is a naive approach : finding all permutations, including the duplicates, and afterwards deleting the duplicates :

def permutations(l):
    if len(l) <=1:
        yield l
    else:
        for p in permutations(l[1:]):
            for i in range(len(l)):
                yield p[:i] + l[0] + p[i:]

print(set(permutations("aabb")))

My question is if their exists a more efficient way to find all these permutations?

EDIT : i do NOT want an approach which follows the inefficient idea of finding all permutations and afterwards deleting the duplicates. My code sample does this already!

EDIT : coldspeed correctly marked my question as duplicate. The correct answer would be to use sympy's multiset_permutations function :

>>> from sympy.utilities.iterables import multiset_permutations
>>> list(multiset_permutations([1,1,1]))
[[1, 1, 1]]
>>> list(multiset_permutations([1,1,2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

, per @Bill Bell.

Do you want to get all the permutations or just their total number? In the latter case there is a simple formula for that — SergGr, Jan 08 '19 at 19:50

score 0 · Answer 1 · answered Jan 08 '19 at 19:50

0

You can use permutations from itertools. The set returns you the unique elements and then you use join to get the strings as a single element. The list comprehension way to do this is following.

from itertools import permutations
result = [''.join(lst) for lst in set((permutations("aabb")))]
print (result)

Output

['aabb', 'baba', 'bbaa', 'abab', 'abba', 'baab']

answered Jan 08 '19 at 19:50

Sheldore

37,862
7
57
71

This is exactly the same as my implementation? – G. Bellaard Jan 08 '19 at 19:59
This is an inbuilt module in itertools which does the same task at the end as you are doing. I do not exactly know under the hood algorithm. You can have a look [here](https://docs.python.org/3/library/itertools.html) – Sheldore Jan 08 '19 at 20:01

mad_ · Answer 2 · 2019-01-08T19:56:22.083

0

Can use permutations and set() to remove duplicates

from itertools import permutations
res=set()
for i in permutations('aabb'):
    res.add(i)

Output

set([('b', 'a', 'b', 'a'), ('b', 'b', 'a', 'a'), ('a', 'b', 'b', 'a'), ('a', 'a', 'b', 'b'), ('b', 'a', 'a', 'b'), ('a', 'b', 'a', 'b')])

If list of strings is desired result

map(''.join,set(permutations('aabb')))

Output

['baba', 'bbaa', 'abba', 'aabb', 'baab', 'abab']

edited Jan 08 '19 at 19:56

answered Jan 08 '19 at 19:51

mad_

8,121
2
25
40

OP's current method is faster than this.(14 µs) This answer takes 15.7 µs – Daniel Scott Jan 08 '19 at 19:56
This is also the same as my implementation. – G. Bellaard Jan 08 '19 at 20:00
1

@DanielScott: That depends on the size of the strings. For ex. try comparing the times for this string `"aabbcdahgfa"` instead of `'aabb'`. Here my answer took 5.66 seconds and OP's method took 21.5 seconds – Sheldore Jan 08 '19 at 20:07

Efficiently finding all possible unique permutations of a word

2 Answers2