Unique permutation generator?

Question

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.

This has been addressed here http://stackoverflow.com/questions/9217839/finding-all-the-unique-permutations-of-the-string — ebarr, Mar 16 '14 at 01:03
Would you please tell what is the order of the best algorithm that you may use to filter some duplicates? I want to know this to think about a prevention algorithm with a better order if exists. — Mohsen Kamrani, Mar 16 '14 at 01:03
Also a python answer is here http://stackoverflow.com/questions/6284396/permutations-with-unique-values?rq=1 — ebarr, Mar 16 '14 at 01:17
ebarr, the solution proposed there doesn't seem to work. I implemented it in Python and it doesn't actually generate any permutations. I think I see why, too: The function is recursive. When called with an empty set, it returns an empty set. During execution, if its sub-calls return an empty set, it returns an empty set. Therefor, it delves down, calls itself with an empty set, then returns empty sets all the way back up. I may have implemented it wrong because it's only psuedo-code... I can show my python implementation if needed. — DanRedux, Mar 16 '14 at 01:23
Why isn't this just `frozenset(itertools.permutations(seq))`? Where there might need to be a conversion to non-mutable objects before applying the frozenset. — jrennie, Mar 16 '14 at 01:25
jrennie, that requires you have the entire list of permutations in memory to convert it to a set. With 11 items that would take all 4gb of my machine's ram. 13 items I might be able to store on my HDD at 596gb. 15 items and I'll have to resort to processing the list on some server farm at 120tb... In practice I have 256 items for which I would need several universes of storage to store the permutations for. (To be specific, I would need a universe for every atom in our universe, and each atom of those universes would need to store 1 whole number for me.) — DanRedux, Mar 16 '14 at 02:36
@DanRedux And yet if all elements are distinct this is exactly how long you are going to wait no matter how smart your algorithm is ;) — Niklas B., Mar 16 '14 at 05:36

score 5 · Answer 1 · edited May 23 '17 at 12:21

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!

Unique permutation generator?

1 Answers1

Linked