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 — Miguel
– Miguel, Commented Apr 13, 2019 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 stackoverflow.com/a/8958309/4996248 — John Coleman
– John Coleman, Commented Apr 13, 2019 at 12:20

gmds · Accepted Answer · 2019-04-13 12:29:21Z

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, 2019 at 12:29

answered Apr 13, 2019 at 12:15

gmds

20k4 gold badges37 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

DobromirM Over a year ago

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.

geckos Over a year ago

Yeah this is the way to go!

Miguel · Accepted Answer · 2019-04-13 12:10:31Z

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, 2019 at 12:10

Miguel

1,35515 silver badges27 bronze badges

Comments

Anthony Kong · Accepted Answer · 2019-04-13 12:18:19Z

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, 2019 at 12:18

Anthony Kong

41.4k52 gold badges192 silver badges325 bronze badges

2 Comments

DobromirM Over a year ago

The islice() approach suggested by @gmds is much more cleaner.

gmds Over a year ago

Note that in Python 3.6, raise StopIteration in a generator will raise a DeprecationWarning; in Python 3.7, it will raise a RuntimeError.

Collectives™ on Stack Overflow

Finite permutations of a list python

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related