permutations with unique values

Question

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.

Answer 1

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.

Answer 2

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