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.

Asked By: xyz-123

||

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.

Answered By: xyz-123

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]]
Answered By: Luka Rahne

Answer #3:

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')
Answered By: Bill Bell

Answer #4:

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.
Answered By: Steven Rumbalski

Answer #5:

You could try using set:

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

The call to set removed duplicates

Answered By: MiniQuark

Answer #6:

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]]
Answered By: Paul Rubel

Answer #7:

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.

Answered By: Little Roys

Answer #8:

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))
Answered By: pylang

Leave a Reply

Your email address will not be published.