21
$\begingroup$

I have an ordered set of symbols S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. I want to find the 1,000,000-th permutation in lexicographic order of S. It is a programming puzzle, but I wanted to figure out a way without brute-forcing the task.

So my thinking was like this:

For 10 variable symbol positions, we have 10! permutations, obviously. Now we want to find the first symbol.

If we fix the first symbol, then the remaining 9 symbols can have 9! combinations.

That means that 0 or 1 cannot be the first symbol, because the highest possible position is 2*9! = 725,760, which is lower than 1,000,000.

The lowest position for a leading 3 is 3*9! + 1 = 1,088,641, so it can't be 3 or higher, either.

Therefore, the first number must be 2. 2*9! is the largest multiple of 9! no greater than 1,000,000, so I need the 2nd symbol (zero-based) from the current set.

So now the question becomes, of the remaining S := S \{2}, which permutation of these symbols is at lexicographic position (1,000,000 - 2*9!) = 274,240?

6*8! = 241,920 is the largest multiple of 8! which is smaller than 274,240, so I need the 6th-smallest symbol of the remaining set, which is 7. So the prefix should be 27 by now.

That way, I keep going and finally arrive at: 1,000,000 = 2*9! + 6*8! + 6*7! + 2*6! + 5*5! + 1*4! + 2*3! + 2*2! + 0*1! + 0*0!

which results in "2783905614" as my solution.

However, according to the solution tester, (free reg. req.) that is incorrect.

Where did I go wrong in thinking or applying?

  • 5
    See also http://en.wikipedia.org/wiki/Factorial_number_system2011-08-30

4 Answers 4

23

To formalize, if $a_0 < ... < a_n$, then in the $k$-th permutation of $\{a_0, ..., a_n\}$ in lexiographic order, the leading entry is $a_q$ if $k = q(n!) + r$ for some $q\ge0$ and $0. (Note that the definition of $r$ here is a bit different from the usual remainder, for which $0\le r< n!$. Also, $a_q$ is the $(q+1)$-th entry but not the $q$-th entry in the sequence, because the index starts from 0.)

    [0 1 2 3 4 5 6 7 8 9] 1000000 = 2(9!) + 274240     2 [0 1 3 4 5 6 7 8 9] 274240 = 6(8!) + 32320     2 7 [0 1 3 4 5 6 8 9] 32320 = 6*(7!) + 2080     2 7 8 [0 1 3 4 5 6 9] 2080 = 2*(6!) + 640     2 7 8 3 [0 1 4 5 6 9] 640 = 5(5!) + 40     2 7 8 3 9 [0 1 4 5 6] 40 = 1(4!) + 16     2 7 8 3 9 1 [0 4 5 6] 16 = 2(3!) + 4     2 7 8 3 9 1 5 [0 4 6] 4 = 1(2!) + 2 <-- we don't write 4 = 2(2!) + 0 here; we need 0
  • 2
    Nice. Wondering how the calculation would change for repeated symbols?2015-12-06
5

Yes, I figured it out. My approach was correct, but I took the wrong number at 1*4!. Silly mistake.

4

I think the above solutions are slightly off. The $k$-th permutation $P_k$ of a string $S$ can be computed as follows (assuming zero-based index):

  • $P_k := \epsilon$
  • while $S \neq \epsilon$:
    • $ f := (|S|-1)!$
    • $i := \lfloor k/f\rfloor$
    • $x := S_i$
    • $k := k \bmod f$
    • append $x$ to $P_k$
    • remove $x$ from $S$
  • return $P_k$

Essentially, this finds the first element of the k-th permutation of S, and then recurses on the remaining string to find its first element.

Depending on whether you start counting your permutations from 0 or 1, the answers is $(2, 7, 8, 3, 9, 1, 5, 6, 0, 4)$ or $(2, 7, 8, 3, 9, 1, 5, 6, 4, 0)$.

Here's a little Python code, implementing the algorithm above as well as its recursive version, then checking correctness for $\vert S\vert=10$ (this might take some time to run):

 from math import factorial, floor  # compute the k-th permutation of S (all indices are zero-based) # all elements in S must be unique  def kthperm(S, k):  #  nonrecursive version     P = []     while S != []:         f = factorial(len(S)-1)         i = int(floor(k/f))         x = S[i]         k = k%f         P.append(x)         S = S[:i] + S[i+1:]     return P   def kthpermrec(S, k):   # recursive version     P = []     if S == []:         return []     else:         f = factorial(len(S)-1)         i = int(floor(k/f))         return [S[i]] + kthpermrec(S[:i] + S[i+1:], k%f)   if __name__ == "__main__":     # This creates the k-th permutations for k=0..len(S)!, and then checks that the result is indeed in lexicographic order.      nrElements = 10     printout = True     result = [] # the list of permutations     for k in xrange(factorial(nrElements)): # loop over all k=0..len(S)!         S = range(nrElements)    # [0, 1, 2, 3, ... , nrElements-1]          p1 = kthperm(S, k)    # compute k-th permutation iteratively         p2 = kthpermrec(S, k)    # compute k-th permutation recursively         assert p1==p2       # make sure the recursive and non-recursive function yield the same permutation         if printout:             print p1         result.append(p1)    # add to list of permutations      for i in xrange(len(result)-1):    # check that permutations are in lexicographic order.         assert result[i] < result[i+1], "Permutations are not sorted, the code is incorrect."         assert len(set(result[i])) == len(result[i]), "Permutation contains multiple copies of an element, the code is incorrect."     assert len(set(result[-1])) == len(result[-1]), "Permutation contains multiple copies of an element, the code is incorrect."    # check on last element     print "The code is correct for |S| = %d." % nrElements    # This line is only reached if no assertion failed, i.e. all permutations are in lexicographic order.       print kthperm(range(10), 1000000)     print kthperm(range(10), 1000001) 
  • 1
    If all indices are zero-based, shouldn't you find `kthperm(range(10), 999999)` instead of `kthperm(range(10), 1000000)`?2015-08-26
0

If you need a tester program that calculate permutation from index or viceversa, you can see here. It can be useful and it's easy to use. It's based on factoradic.

As example: it allows to calculate the correct index corresponding to the solution "2783905614" mentioned earlier Or obtain the 2,000,000th permutation of S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } )

It works up to 17 elements (max index = 355,687,428,096,000)