Finite permutations of a list python

Question

I have a list and would like to generate a finite number of permutation with no repeated elements.

itertools.permutations(x)

gives all possible orderings but I only need a specific number of permutation. (my initial list contains ~200 elements => 200! will take an unreasonable amount of time and I don't need all of them)

what I have done so far

def createList(My_List):
    New_List = random.sample(My_List, len(My_List))
    return New_List

def createManyList(Nb_of_Lists):
    list_of_list = []
    for i in range(0, Nb_of_Lists):
        list_of_list.append(createList())
    return list_of_list

It's working but my List_of_list will not have unique permutations or at least I have no guaranty about it.

Is there any way around to do so? Thanks

Possible duplicate of [Limiting the number of combinations /permutations in python](https://stackoverflow.com/questions/23722473/limiting-the-number-of-combinations-permutations-in-python) — Miguel, Apr 13 '19 at 12:15
Are you looking for a random sample of all permutations? If so -- you can pick a random set of numbers in [0 to 200!-1] and unrank them, using an algorithm like https://stackoverflow.com/a/8958309/4996248 — John Coleman, Apr 13 '19 at 12:20

gmds · Accepted Answer · 2019-04-13T12:29:21.397

5

Just use islice, which allows you to take a number of elements from an iterable:

from itertools import permutations, islice

n_elements = 1000

list(islice(permutations(x), 0, 1000))

This will return a list of (the first) 1000 permutations.

The reason this works is that permutations returns an iterator, which is an object that generates values to return as they are needed, not immediately. Therefore, the process goes something like this:

The calling function (in this case, list) asks for the next value from islice
islice checks if 1000 values have been returned; if not, it asks for the next value from permutations
permutations returns the next value, in order

Because of this, the full list of permutations never needs to be generated; we take only as many as we want.

edited Apr 13 '19 at 12:29

answered Apr 13 '19 at 12:15

gmds

19,325
4
32
58

This is the best solution. You might want to add a brief explanation why generators are efficient in python and that all permutations are not actually created and then filtered down to 1000. – DobromirM Apr 13 '19 at 12:22
Yeah this is the way to go! – geckos Apr 13 '19 at 12:28

score 1 · Answer 2 · answered Apr 13 '19 at 12:10

1

You can do:

i = 0
while i < Nb_of_Lists:
    if createlist() not in list_of_lists:
        list_of_list.append(createList())
    else:
        i -= 1

This will check if that permutation was already used.

answered Apr 13 '19 at 12:10

Miguel

1,295
12
25

score 1 · Answer 3 · answered Apr 13 '19 at 12:18

1

You don't need to roll your own permutation. You just to halt the generator once you get enough:

# python 2.7
import random
import itertools
def createList(My_List):
    New_List = random.sample(My_List, len(My_List))
    return New_List

x = createList(xrange(20))
def getFirst200():
    for i, result in enumerate(itertools.permutations(x)):
        if i == 200:
            raise StopIteration
        yield result

print list(getFirst200()) # print first 200 of the result

This is faster and more memory efficient than 'generate of full set then take first 200' approach

answered Apr 13 '19 at 12:18

Anthony Kong

37,791
46
172
304

The `islice()` approach suggested by @gmds is much more cleaner. – DobromirM Apr 13 '19 at 12:24
Note that in Python 3.6, `raise StopIteration` in a `generator` will raise a `DeprecationWarning`; in Python 3.7, it will raise a `RuntimeError`. – gmds Apr 13 '19 at 12:30

Finite permutations of a list python

3 Answers3