20
$\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?

$\endgroup$
  • 1
    $\begingroup$ The solution is $2783915460$, you can find many explainations on how to get when seeing the solution-page. $\endgroup$ – Listing Aug 30 '11 at 16:32
  • 3
    $\begingroup$ Shouldn't 1*4! result in a 1 digit, not 0? $\endgroup$ – Ross Millikan Aug 30 '11 at 16:39
  • 1
    $\begingroup$ Won't that term $1*4!$ mean that the sixth digit shoud be $1$, not $0$? $\endgroup$ – Jyrki Lahtonen Aug 30 '11 at 16:40
  • 5
    $\begingroup$ See also en.wikipedia.org/wiki/Factorial_number_system $\endgroup$ – Ilmari Karonen Aug 30 '11 at 21:54
23
$\begingroup$

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<r\le n!$. (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<r<=2!
    2 7 8 3 9 1 5 4 [0 6]
2 = 1(1!) + 1
    2 7 8 3 9 1 5 4 6 [0]
$\endgroup$
  • 2
    $\begingroup$ Thanks, your scheme explains itself. $\endgroup$ – jonaprieto Jun 3 '13 at 2:40
  • 2
    $\begingroup$ Nice. Wondering how the calculation would change for repeated symbols? $\endgroup$ – Abu Bakar Dec 6 '15 at 3:46
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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)
$\endgroup$
  • 1
    $\begingroup$ If all indices are zero-based, shouldn't you find kthperm(range(10), 999999) instead of kthperm(range(10), 1000000)? $\endgroup$ – user1551 Aug 26 '15 at 7:19
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.