0

What will be an efficient way to generate unique permutations of a list?

I tried this

set(itertools.permutations(['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']))

But, as the number of different elements in the list increases, it takes too long. Sometimes even freezing the PC.

Anoop A
  • 1
  • 1
  • 1
    Does this answer your question? [Generating Unique Permutations in Python](https://stackoverflow.com/questions/15592299/generating-unique-permutations-in-python) – Karthik Aug 30 '20 at 07:50
  • What do you need to do with them ? Because you can generate just a fews by iterating over the result of `itertools.permutations` because using a `set()` it force to WAIT until ALL the permutations are build which, yes, can be quite a long (hours, days, ...) – azro Aug 30 '20 at 07:57
  • @Karthik, speed is the issue. I tried using ```set```. The other answer in this link is said to be slower than the set method. – Anoop A Aug 31 '20 at 05:31
  • @azro I have to iterate over each permutation. Each permutation will be used for an expensive calculation. The result of itertools.permutations() contains duplicate elements. – Anoop A Aug 31 '20 at 05:40
  • What the code giving in the answer of @fusion sees right for your purpose – azro Aug 31 '20 at 05:59

2 Answers2

1

If you don't need to get all the possible permutations and the list is very long, you can use random.shuffle and check if the resulting permutation has already been generated on the go.

An example would be like this:

import random 

a = [a very long list]

existed_permutations = set()

for i in range(10):
    random.shuffle(a)
    # shuffle a in place
    new_permutation = tuple(a)
    if new_permutation in existed_permutations:
        continue 
    else:
        print(new_permutation)
        existed_permutations.add(new_permutation)

However, if your list is very long and you need all the permutations, there might not be an easy way to speed things up.

fusion
  • 1,327
  • 6
  • 12
  • Did you mean the first element of tubple(a)? ```new_permutation = tuple(a)[0]``` – Anoop A Aug 31 '20 at 06:14
  • @fustion I like the idea of taking random permutations when the number of permutations is large. I checked the timing for the following. ```l = ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b'] a = list(itertools.permutations(l)) random.shuffle(a)``` perumuation took 7 minutes and shuffle took 47 minutes. – Anoop A Aug 31 '20 at 12:53
0

Taking input from itertools recipes.and answer from @fusion, I think the following code works.

def random_permutation(iterable, r=None):
    "Random selection from itertools.permutations(iterable, r)"
    pool = tuple(iterable)
    r = len(pool) if r is None else r
    return tuple(random.sample(pool, r))


l = ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b']

t_start = time.clock()

existed_permutations = set()

for _ in range(10):
    new_permutation = random_permutation(l)
    if new_permutation in existed_permutations:
        print("dup")
        continue
    else:
        print(new_permutation)
        existed_permutations.add(new_permutation)

t_total = time.clock()
print("total time", t_total-t_start)
Anoop A
  • 1
  • 1