Prevent Duplicates From Itertools.permutations

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): pri

Solution 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 inset(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).

Solution 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, combinationsdicta= {}
perm = permutations('AABB', 4)
for i in list(perm):
    if i in dicta:
        dicta[i] += 1else:
        dicta[i] = 1
print([i for i in dicta.keys()])

Solution 3:

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      --->thisis first output.

2nd      1st
 A        A    ----> thisis 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"

Solution 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 inset(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