# permutations with unique values

Posted on

Solving problem is about exposing yourself to as many situations as possible like permutations with unique values and practice these strategies over and over. With time, it becomes second nature and a natural way you approach any problems in general. Big or small, always start with a plan, use other strategies mentioned here till you are confident and ready to code the solution.
In this post, my aim is to share an overview the topic about permutations with unique values, which can be followed any time. Take easy to follow this discuss.

permutations with unique values

itertools.permutations generates where its elements are treated as unique based on their position, not on their value. So basically I want to avoid duplicates like this:

``````>>> list(itertools.permutations([1, 1, 1]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]
``````

Filtering afterwards is not possible because the amount of permutations is too large in my case.

Does anybody know of a suitable algorithm for this?

Thank you very much!

EDIT:

What I basically want is the following:

``````x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))
``````

which is not possible because `sorted` creates a list and the output of itertools.product is too large.

Sorry, I should have described the actual problem.

``````class unique_element:
def __init__(self,value,occurrences):
self.value = value
self.occurrences = occurrences
def perm_unique(elements):
eset=set(elements)
listunique = [unique_element(i,elements.count(i)) for i in eset]
u=len(elements)
return perm_unique_helper(listunique,[0]*u,u-1)
def perm_unique_helper(listunique,result_list,d):
if d < 0:
yield tuple(result_list)
else:
for i in listunique:
if i.occurrences > 0:
result_list[d]=i.value
i.occurrences-=1
for g in  perm_unique_helper(listunique,result_list,d-1):
yield g
i.occurrences+=1
a = list(perm_unique([1,1,2]))
print(a)
``````

result:

``````[(2, 1, 1), (1, 2, 1), (1, 1, 2)]
``````

EDIT (how this works):

I rewrote the above program to be longer but more readable.

I usually have a hard time explaining how something works, but let me try.
In order to understand how this works, you have to understand a similar but simpler program that would yield all permutations with repetitions.

``````def permutations_with_replacement(elements,n):
return permutations_helper(elements,[0]*n,n-1)#this is generator
def permutations_helper(elements,result_list,d):
if d<0:
yield tuple(result_list)
else:
for i in elements:
result_list[d]=i
all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
for g in all_permutations:
yield g
``````

This program is obviously much simpler:
d stands for depth in permutations_helper and has two functions. One function is the stopping condition of our recursive algorithm, and the other is for the result list that is passed around.

Instead of returning each result, we yield it. If there were no function/operator `yield` we would have to push the result in some queue at the point of the stopping condition. But this way, once the stopping condition is met, the result is propagated through all stacks up to the caller. That is the purpose of
`for g in perm_unique_helper(listunique,result_list,d-1): yield g`
so each result is propagated up to caller.

Back to the original program:
we have a list of unique elements. Before we can use each element, we have to check how many of them are still available to push onto result_list. Working with this program is very similar to `permutations_with_replacement`. The difference is that each element cannot be repeated more times than it is in perm_unique_helper.

Because sometimes new questions are marked as duplicates and their authors are referred to this question it may be important to mention that sympy has an iterator for this purpose.

``````>>> 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]]
``````

This relies on the implementation detail that any permutation of a sorted iterable are in sorted order unless they are duplicates of prior permutations.

``````from itertools import permutations
def unique_permutations(iterable, r=None):
previous = tuple()
for p in permutations(sorted(iterable), r):
if p > previous:
previous = p
yield p
for p in unique_permutations('cabcab', 2):
print p
``````

gives

``````('a', 'a')
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'b')
('b', 'c')
('c', 'a')
('c', 'b')
('c', 'c')
``````

Roughly as fast as Luka Rahne’s answer, but shorter & simpler, IMHO.

``````def unique_permutations(elements):
if len(elements) == 1:
yield (elements[0],)
else:
unique_elements = set(elements)
for first_element in unique_elements:
remaining_elements = list(elements)
remaining_elements.remove(first_element)
for sub_permutation in unique_permutations(remaining_elements):
yield (first_element,) + sub_permutation
>>> list(unique_permutations((1,2,3,1)))
[(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), ... , (3, 1, 2, 1), (3, 2, 1, 1)]
``````

It works recursively by setting the first element (iterating through all unique elements), and iterating through the permutations for all remaining elements.

Let’s go through the `unique_permutations` of (1,2,3,1) to see how it works:

• `unique_elements` are 1,2,3
• Let’s iterate through them: `first_element` starts with 1.
• `remaining_elements` are [2,3,1] (ie. 1,2,3,1 minus the first 1)
• We iterate (recursively) through the permutations of the remaining elements: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
• For each `sub_permutation`, we insert the `first_element`: (1,1,2,3), (1,1,3,2), … and yield the result.
• Now we iterate to `first_element` = 2, and do the same as above.
• `remaining_elements` are [1,3,1] (ie. 1,2,3,1 minus the first 2)
• We iterate through the permutations of the remaining elements: (1, 1, 3), (1, 3, 1), (3, 1, 1)
• For each `sub_permutation`, we insert the `first_element`: (2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1)… and yield the result.
• Finally, we do the same with `first_element` = 3.

You could try using set:

``````>>> list(itertools.permutations(set([1,1,2,2])))
[(1, 2), (2, 1)]
``````

The call to set removed duplicates

This is my solution with 10 lines:

``````class Solution(object):
def permute_unique(self, nums):
perms = [[]]
for n in nums:
new_perm = []
for perm in perms:
for i in range(len(perm) + 1):
new_perm.append(perm[:i] + [n] + perm[i:])
# handle duplication
if i < len(perm) and perm[i] == n: break
perms = new_perm
return perms
if __name__ == '__main__':
s = Solution()
print s.permute_unique([1, 1, 1])
print s.permute_unique([1, 2, 1])
print s.permute_unique([1, 2, 3])
``````

— Result —-

``````[[1, 1, 1]]
[[1, 2, 1], [2, 1, 1], [1, 1, 2]]
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
``````

A naive approach might be to take the set of the permutations:

``````list(set(it.permutations([1, 1, 1])))
# [(1, 1, 1)]
``````

However, this technique wastefully computes replicate permutations and discards them. A more efficient approach would be `more_itertools.distinct_permutations`, a third-party tool.

Code

``````import itertools as it
import more_itertools as mit
list(mit.distinct_permutations([1, 1, 1]))
# [(1, 1, 1)]
``````

Performance

Using a larger iterable, we will compare the performances between the naive and third-party techniques.

``````iterable = [1, 1, 1, 1, 1, 1]
len(list(it.permutations(iterable)))
# 720
%timeit -n 10000 list(set(it.permutations(iterable)))
# 10000 loops, best of 3: 111 µs per loop
%timeit -n 10000 list(mit.distinct_permutations(iterable))
# 10000 loops, best of 3: 16.7 µs per loop
``````

We see `more_itertools.distinct_permutations` is an order of magnitude faster.

Details

From the source, a recursion algorithm (as seen in the accepted answer) is used to compute distinct permutations, thereby obviating wasteful computations. See the source code for more details.

Here is a recursive solution to the problem.

``````def permutation(num_array):
res=[]
if len(num_array) <= 1:
return [num_array]
for num in set(num_array):
temp_array = num_array.copy()
temp_array.remove(num)
res += [[num] + perm for perm in permutation(temp_array)]
return res
arr=[1,2,2]
print(permutation(arr))
``````