Prevent duplicates from itertools.permutations

Question

I want to get all the unique permutations for a 4 character string using 2 A and 2 B

from itertools import permutations

perm = permutations('AABB', 4)
for i in list(perm):
    print(i)

This gets me

('A', 'A', 'B', 'B')
('A', 'A', 'B', 'B')
('A', 'B', 'A', 'B')
('A', 'B', 'B', 'A')
...

As you can see I get duplicates. I guess this is because it treats the A in the 1st place and 2nd place are different values, but to me AABB is simply 1 unique result.

I can workaround this results by throwing all of them into a set to get rid of the dups, but I think I'm just using the permutation function wrong.

How do I use permutation function to get all the unique permutations with using 2 A's and 2 B's without getting the dups?

Answer 1

There is no direct way to do that in itertools. The documentation for permutations() states:

Elements are treated as unique based on their position, not on their value.

This means that though the two As look equal to you, itertools treats them as if they are not equal, since they have different positions in the original string.

The number of the results you want is called the multinomial coefficient for 4 values, 2 equal and 2 others equal. You could get what you want by coding your own equivalent function to permutations but that would take a while to code and debug. (Perhaps call it multinomial though that word refers to a number, not the actual lists.) An easier way, perhaps slower in execution and memory usage but much faster in programming, is to use permutations and Python's set to remove the duplicates. You could do this:

from itertools import permutations

perm = permutations('AABB', 4)
for i in set(perm):
    print(i)

This may result in a different order to the printout. If you want to restore the original order, use sorted(set(perm)), since permutations returns in lexicographical order (if your original string was in sorted order).

Answer 2

You should use more_itertools.distinct_permutations to achieve this.

from more_itertools import distinct_permutations as idp
for p in idp('ABB'):
    print(p)

Answer 3

You can iterate over set or use hashing

from itertools import permutations, combinations

perm = set(permutations('AABB', 4))
for i in <b>perm</b>:
    print(i)

#Output
('A', 'A', 'B', 'B')
('A', 'B', 'A', 'B')
('A', 'B', 'B', 'A')
('B', 'A', 'A', 'B')
('B', 'B', 'A', 'A')
('B', 'A', 'B', 'A')  

Using dictionary:

from itertools import permutations, combinations
dicta = {}
perm = permutations('AABB', 4)
for i in list(perm):
    if i in dicta:
        dicta[i] += 1
    else:
        dicta[i] = 1
print([i for i in dicta.keys()])

Answer 4

You are pretty much right, itertools treats elements on their positions not on their values - therefore, it does not offer support to remove these types of repeats...

We know this from the documentation which states that:

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.

This leaves us with two options, either write your own function, or convert to a set instead of a list:

from itertools import permutations

perm = permutations('AABB', 4)
for i in set(perm):
    print(i)

which outputs:

('A', 'B', 'B', 'A')
('B', 'A', 'B', 'A')
('B', 'B', 'A', 'A')
('A', 'B', 'A', 'B')
('A', 'A', 'B', 'B')
('B', 'A', 'A', 'B')

Note that there is no need to convert the set back to a list as you can iterate over a set

Answer 5

The above output is not wrong.First understand how permutation works.

s = "AA"

For above string, the permutations will give 2 strings.

AA and AA

The above two strings are completely valid because

1st      2nd
 A        A      --->this is first output.

2nd      1st
 A        A    ----> this is 2nd one.

What permutation does is just replace the position of characters. Unfortunately, it does not check for any duplicates. To remove the duplicates, you can use Sets, since sets does not allow any duplicate values.

myList = ["AA", "AB", "AA"]
set(myList)
output---> "AA", "AB"