I would like to get the Nth element of a permutation list without creating all of the permutations
If I execute perm = permutations(range(3)) I get:
(0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0)
And I can get the 4th element by doing perm[3] that is (1, 2, 0)
The problem comes when I want to get the 12843175th element of permutations(range(12)) or higher because my computer causes memory error
Is there a more optimal way to obtain this value?
2 approaches to extract a permutation at the needed position:
1) The fastest one: with itertools.islice to return an element at specific offsets:
from itertools import permutations, islice
def get_nth_permuted(rng, pos):
return next(islice(permutations(rng), pos, None), None)
print(get_nth_permuted(range(40), 72843175))
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 38, 28, 36, 35, 30, 31, 34, 33, 32, 39, 37)
2) A more straightforward, but much slower is traversing over iterator and capture/yield the value only at the needed position:
from itertools import permutations
def get_nth_permuted(rng, pos):
return next((v for i, v in enumerate(permutations(rng)) if i == pos), None)
print(get_nth_permuted2(range(40), 72843175))
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 38, 28, 36, 35, 30, 31, 34, 33, 32, 39, 37)