xyz-123 xyz-123 - 1 month ago 11
Python Question

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.

Answer
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 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,[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 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.

Comments