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)]
x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))
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,*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)
[(2, 1, 1), (1, 2, 1), (1, 1, 2)]
EDIT (how this works):
I rewrite upper program to be longer but more readable I have usually hard time to explain how something works, but let me try. In order to understand how this works you have to understand similar, but simpler program that would yield all permutations with repetition.
def permutations_with_replecement(elements,n): return permutations_helper(elements,*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 in obviously much simpler. d stands for depth in permutations_helper and has two functions. One function is stopping condition of our recursive algorithm and other is for result list, that is passed around.
Instead of returning each result we yield it. If there were no function/operator
yield we had to push result in some queue at point of stopping condition. But this way once stopping condition is meet result is propagated trough all stack up to the caller. That is purpouse of
for g in perm_unique_helper(listunique,result_list,d-1): yield g
so each result is propagated up to caller.
Back to original program:
We have list of unique elements. Before we can use each element, we have to check how many of them are still available to push it on result_list. Working of this program is very similar compared to
permutations_with_replecement difference is that each element can not be repeated more times that is in perm_unique_helper.