CODEWITHSUNDEEP
pythonalgorithmpermutation
DanRedux
DanRedux

Reputation: 9349

Unique permutation generator?

The problem: I have some list of numbers, like [1,1,2]. I need to generate the unique permutations. The permutations are [1,1,2],[1,1,2],[1,2,1],[1,2,1],[2,1,1],[2,1,1]. I need to only generate the unique permutations, i.e., [1,1,2],[1,2,1],[2,1,1].

My attempt: My first attempt was to keep a set of existing permutations, and create a filter for the itertools.permutations generator that would use the set to filter out duplicates. However, for efficiency reasons, I would rather not generate those permutations in the first place. Even for a small list of 12 numbers, only 1% of them are unique.

I have the start of an idea that I can't seem to figure out all the way: I could create permutations of the unique values in my list, i.e., [1,2], put the remaining numbers in all the different places.

Thanks for any help, and to be clear, I do not want to filter out duplicate permutations, I want to generate only unique permutations in the first place.

Upvotes: 4

Views: 558

Answers (1)

bbayles
bbayles

Reputation: 4507

I adapted this code from a previous Stack Overflow answer:

def distinct_permutations(seq):
  from collections import Counter

  def perm_unique_helper(item_counts, perm, i):
    if i < 0:
      yield tuple(perm)
    else:
      for item in item_counts:
        if item_counts[item] <= 0:
          continue
        perm[i] = item
        item_counts[item] -= 1
        # In Python < 3.3 you can replace the yield from with a loop
        yield from perm_unique_helper(item_counts, perm, i - 1)
        item_counts[item] += 1

  item_counts = Counter(seq)
  L = len(seq)

  return perm_unique_helper(item_counts, [0] * L, L - 1)

My laptop can't do length-11 input sequences with the set(permutations(seq)) method, but with this method it can!

Upvotes: 5

Related Questions