2
\$\begingroup\$

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

import itertools


def lexicographic(n, digits):
    """Assumes digits a string.
    returns the nth item of the lexicographic permutation of digits."""
    return list(itertools.permutations(digits))[n - 1]


if __name__ == '__main__':
    permutation = list(lexicographic(1000000, '0123456789'))
    print(''.join(permutation))
\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

You’re building up a huge list of permutations in order to get to exactly one permutation. This is needlessly using time (computing all permutations that come before it) and memory (storing all those permutations in a list.

If you have 9 objects, you can have 9! = 3,628,800 permutations. So with the 10 digits, 0 through 9, the first 362,880 permutations will be 0#########, the next 362,880 permutations will be 1#########, and you’ll reach the millionth permutation 274,240 permutations in to the 2#########’s. So, 1 digit down, 9 to go.

With 8 objects, you can have 8! = 40,320 permutations. Again, you can determine you’ll cross the 274,240’th permutation during the 7th group of permutations of the 9 objects: 013456789 ... so the your millionth permutation will be of the form 27########.

Repeat for the rest of the digits: a calculator works fine. Or write a program to solve this, and the answer will be returned directly in a fraction of a second.

\$\endgroup\$
1
\$\begingroup\$

itertools.islice()

Looks pretty good, but generating a list of all the permutations can take a lot of memory. Use itertools.islice() to skip over the first 999,999 permutations that you don't want. The indexing parameters to islice are just like for range(start, stop, step)

def lexicographic(n, digits):
    """Assumes digits a string.
    returns the nth item of the lexicographic permutation of digits."""

    full_sequence = itertools.permutations(digits)
    starting_at_n = itertools.islice(full_sequence, n-1, n)
    return next(starting_at_n)

you may need to adjust the n-1 part depending on whether the problem counts from zero or 1.

This still iterates over all the permutations, so it isn't very efficient for large sequences. With some math you can determine the permutation without iterating them.

\$\endgroup\$

You must log in to answer this question.