permutations with repetition in python(to don t use set() or uniform() method )

Question

I have a list like this:

from itertools import permutations
l = [1,1,1,1,1,1,1,2]

The duplicate '1' entries in the original list mean that the distinct permutations only depend on where the '2' appears in the output; so there are only 8 distinct permutations. But the permutations() function will generate all factorial(8)=40320 permutations. I know I can remove duplicate outputs using set() function after the fact, but the algorithm is still O(N!) and I would like something more efficient.

what do you mean "on the spot of 2"? reframe your question. Unable to understand what you meant. — Bhanu Tez, Apr 03 '19 at 23:10
Possible duplicate of [permutations with unique values](https://stackoverflow.com/questions/6284396/permutations-with-unique-values) — IvyMike, Apr 04 '19 at 02:33

score 0 · Answer 1 · answered Apr 04 '19 at 02:40

Here are several efficient solutions which not use set, basically about avoid inserting duplicated element.

# To handle duplication, just avoid inserting a number before any of its duplicates.
def permuteUnique1(nums):
    ans = [[]]
    for n in nums:
        new_ans = []
        for l in ans:
            for i in range(len(l) + 1):
                new_ans.append(l[:i] + [n] + l[i:])
                if i < len(l) and l[i] == n: break  # handles duplication
        ans = new_ans
    return ans


# Duplication happens when we insert the duplicated element before and after the same element,
# to eliminate duplicates, just insert only after the same element.
def permuteUnique2(nums):
    if not nums:
        return []
    nums.sort()
    ans = [[]]
    for n in nums:
        new_ans = []
        l = len(ans[-1])
        for seq in ans:
            for i in range(l, -1, -1):
                if i < l and seq[i] == n:
                    break
                new_ans.append(seq[:i] + [n] + seq[i:])
        ans = new_ans
    return ans


# Build the list of permutations one number at a time, insert the number into each already built permutation
# but only before other instances of the same number, never after.
def permuteUnique3(nums):
    perms = [[]]
    for n in nums:
        perms = [p[:i] + [n] + p[i:]
                 for p in perms
                 for i in range((p + [n]).index(n) + 1)]
    return perms


# or as "one-liner" using reduce:
from functools import reduce
def permuteUnique4(nums):
    return reduce(lambda perms, n: [p[:i] + [n] + p[i:]
                                    for p in perms
                                    for i in range((p + [n]).index(n) + 1)],
                  nums, [[]])

you can find more solutions and expaination in LeetCode. Hope that will help you, and comment if you have further questions. : )

permutations with repetition in python(to don t use set() or uniform() method )

1 Answers1