CODEWITHSUNDEEP
pythonpython-3.xalgorithm
page290
page290

Reputation: 39

Find the i'th permutation of a list in Python?

Wounder if it is possible to create a lazy generator for all the permutations of a particular list? I need all permutations of a list [1 ... 2^6]. Doing something like list(itertools.permutations([i for i in range(1, 2**6)])) is just way too much for my PC to handle, so what I would like to do is a lazy evaluator that only calculate the i'th permutation.

In haskell for example this would be some form of lazy evaluator, but is it possible to do the same in Python? Is it also/otherwise maybe some known algorithm to find the i'th iteration of a list that I do not know about?

Upvotes: 1

Views: 163

Answers (1)

Stef
Stef

Reputation: 15525

Two ways to answer your question:

  • itertools.permutations is already lazy; it returns a generator, and will only evaluate the permutations as you ask for them, either one by one with next, or all at once with list, or iterating over it in a for-loop, or some other way;
  • The exact function you're asking for is implemented in module more_itertools: more_itertools.nth_permutation.

Demonstration:

from itertools import permutations
from more_itertools import nth_permutation

g = permutations('abc')
print( next(g) )
# ('a', 'b', 'c')
print( next(g) )
# ('a', 'c', 'b')
print( next(g) )
# ('b', 'a', 'c')
print( list(g) ) # will omit the three permutations already extracted with next
# [('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

print( nth_permutation('abcdefg', 7, index=16) )
# ('a', 'b', 'c', 'f', 'g', 'd', 'e')

Upvotes: 2

Related Questions