Duplicates in list of permutations

Question

I am using the permutations function from the itertools library to print a list of permutations for a string. In this case, it is baca. However, the output list has duplicates of each element element. Here it is:

['aabc', 'aabc', 'aacb', 'aacb', 'abac', 'abac', 'abca', 'abca', 'acab', 'acab', 'acba', 'acba', 'baac', 'baac', 'baca', 'baca', 'bcaa', 'bcaa', 'caab', 'caab', 'caba', 'caba', 'cbaa', 'cbaa']

Here is my code. It's pretty straight forward. I don't see anything in my code that would produce this behavior.

from itertools import permutations

def rearrangeWord(word):
    p = [''.join(i) for i in permutations(word) ]
    print(sorted(p))

rearrangeWord('baca')

I think this is happening because you have two `a`s in your string `baca`. If you want to only have one of each letter, use `permutations(set(word))` instead. — Ed Ward, Aug 22 '20 at 19:22
@EdWard But what that does is that it prints strings where each letter occurs only once. I want to have permutations where every letter occurs as many times as they exist. — Onur-Andros Ozbek, Aug 22 '20 at 19:23
as there are 2 'a' in your string it is obvious you will get duplicates, see https://www.geeksforgeeks.org/distinct-permutations-string-set-2/ — Ajay, Aug 22 '20 at 19:24
From documentation on itertools.product: "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 in each permutation." https://stackoverflow.com/questions/6284396/permutations-with-unique-values — mitoRibo, Aug 22 '20 at 19:26

Chris Charley · Accepted Answer · 2020-08-22T19:52:57.997

multiset_permutations can find the permutations with multiple items.

>>> from sympy.utilities.iterables import multiset_permutations
>>> s = 'baca'


>>> for item in multiset_permutations(s):
    print(item)


['a', 'a', 'b', 'c']
['a', 'a', 'c', 'b']
['a', 'b', 'a', 'c']
['a', 'b', 'c', 'a']
['a', 'c', 'a', 'b']
['a', 'c', 'b', 'a']
['b', 'a', 'a', 'c']
['b', 'a', 'c', 'a']
['b', 'c', 'a', 'a']
['c', 'a', 'a', 'b']
['c', 'a', 'b', 'a']
['c', 'b', 'a', 'a']

mlisthenewcool · Answer 2 · 2020-08-22T19:50:51.313

2

You are duplicating all 'aa' permutations.

print(sorted(set(p)))

edited Aug 22 '20 at 19:50

answered Aug 22 '20 at 19:24

mlisthenewcool

539
3
14

2

You don't need to call `list()`, `sorted` can sort any iterable. – Jasmijn Aug 22 '20 at 19:46

score 1 · Answer 3 · answered Aug 22 '20 at 19:55

1

If you sort the word first (which is much cheaper), you don't need to sort afterwards:

>>> [*dict.fromkeys(map(''.join, permutations(sorted('baca'))))]
['aabc', 'aacb', 'abac', 'abca', 'acab', 'acba', 'baac', 'baca', 'bcaa', 'caab', 'caba', 'cbaa']

answered Aug 22 '20 at 19:55

superb rain

5,300
2
11
25

score 0 · Answer 4 · answered Aug 22 '20 at 19:31

0

This solved my problem:

print(sorted(dict.fromkeys(p)))

Now this is the output:

['aabc', 'aacb', 'abac', 'abca', 'acab', 'acba', 'baac', 'baca', 'bcaa', 'caab', 'caba', 'cbaa']

answered Aug 22 '20 at 19:31

Onur-Andros Ozbek

2,998
2
29
78

Duplicates in list of permutations

4 Answers4