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 can iterate over set or use hashing

from itertools import permutations, combinations

perm = set(permutations('AABB', 4))
for i in perm:
    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()])