3
$\begingroup$

$N$ objects can be arranged in $N!$ different orders. For example, $10$ playing cards can be stacked $10! = 3,628,800$ different ways. Is there a way to assign a numerical value to each permutation so that every integer from $1$ to $N!$ corresponds to exactly one permutation? Is there a way to derive the permutation from the corresponding numerical value?

$\endgroup$
3
  • $\begingroup$ Well, there are many ways: just ennumerate arbitrarily the permutations from $1$ to $\,N!\,$ $\endgroup$
    – DonAntonio
    Mar 12 '13 at 3:05
  • $\begingroup$ This is discussed in detail in Higher-Order Perl, section 4.3.1, pp. 128–135, which is available online. It is also discussed in exhaustive detail in volum IV of Knuth's The Art of Computer programming. $\endgroup$
    – MJD
    Mar 12 '13 at 3:41
  • $\begingroup$ Could you not number each card and then name permutations according to the order? $\endgroup$ Mar 12 '13 at 4:59
2
$\begingroup$

I don't know if there is a standard way of doing this but you could do something like this:

Lets take 4 playing cards b/c it is more managable. Order them some way, say label them a,b,c,d and put them in the order (a,b,c,d). Then

$$1:(a,b,c,d)\\ 2:(a,b,d,c)\\ 3:(a,c,b,d)\\ 4:(a,c,d,b)\\ 5:(a,d,b,c)\\ 6:(a,d,c,b) $$ So fixing "a" as the first entry gives 6 possible permutations, repeating this for b,c,d in the first entry will give you the other 18, for a total of 24. The method is to first fix an ordering and then permute only the last 2, then once thats done permute the last 3 and so on.

$\endgroup$
3
  • 1
    $\begingroup$ No help so far. $\endgroup$ Mar 12 '13 at 15:47
  • $\begingroup$ Im not sure what your asking then, you asked if there was a way to assign a number to each permutation. The answer is yes, and here is one way of doing it systematically. $\endgroup$
    – mv3
    Mar 12 '13 at 16:03
  • $\begingroup$ And if you know the original ordering of the objects, (a,b,c,d) then you can reconstruct the permutation from the value $\endgroup$
    – mv3
    Mar 12 '13 at 16:08
2
$\begingroup$

Yes. The easiest way is to order them lexicographically. So for $\{0,1,2,3,4\}$ there are $120$ permutations, from $01234$ to $43210$. It is easiest if our permutation numbers run from $0$ to $119$. Of these $4!=24$ have each number first, so if you want permuation $n$, the first number is $a_0=\lfloor \frac n{24} \rfloor$. Then of those, there are $3!=6$ that have each of the remaining numbers first. To find it, compute $a_1=\lfloor \frac {n-24a_0}6 \rfloor$, then increment by $1$ if $a_0 \le a_1$ because you want the $a_1$st of what is left. Now recurse.

$\endgroup$
3
  • $\begingroup$ I'm looking for a function. Suppose ten cards are in the order Ace-2-3-4-5-6-7-8-9-10 when arranged in permutation #1. What would permutation #1,000,000 look like? Suppose the cards are in the order 5-9-2-4-10-Ace-3-8-6-7. Which permutation # (an integer between 1 and 3,628,800) would that be? Maybe what I'm asking just isn't possible, but it would be useful to me if it can be done. $\endgroup$ Mar 12 '13 at 16:09
  • $\begingroup$ @LeroyNimka: It is quite possible. For permutation 1,000,000 the first card is $\lfloor\frac {999,999}{9!}\rfloor+1=3$ where the -1 and +1 come because you are counting from 1. The ones starting with Ace and 2 use up $2\cdot 9!=725760$ so now we want permutation 274240 of the rest. $\lfloor\frac {274239}{8!}\rfloor+1=7$ so we want the seventh card, the $8$. That has used up $6 \cdot 8!=241920$, so we need the $32320$ of the rest, the seventh one, the 9. So we have started with 389. This can be written in a few tens of lines with a loop. $\endgroup$ Mar 12 '13 at 16:27
  • $\begingroup$ @LeroyNimka: for the other direction, the 5 leads off starting with permutation $4 \cdot 9!+1=1451521. Having the 9 next adds $7 \cdot 8!=282240. The 2 next adds $7!=5040$, so we are up to 1738801. Again, keep going, and again a few tens of lines. $\endgroup$ Mar 12 '13 at 16:30
1
$\begingroup$

Notice that for one and the same letter kept, out of $n$, in one position, you have $(n-1)!$ possible choices. And that is all that you need.

$4231, n=4$

Before we reached $4$ we had $(4-1)(n-1)!$ permutations. With $4$ fixed we had $(2-1)(n-2)!$ options. With $42$ fixed we had $(3-1-1)(n-3)!$ options as $2$ is preceding $3$ and is to the left of it. With $423$ fixed we had $(1-1)(n-4)!$ options. It is $18$th permutation.

Formula is then:

$$P(a_1a_2...a_m)=\sum_{k=1}^{m}(\alpha_r(a_k)-1)(m-k)!$$

where $\alpha_r(a_k)$ is $1$-based alphabetical position of symbol $a_k$ reduced by the number of symbols that appear earlier in the alphabet and appear to the left of it.

Inverse is more or less obvious. Essentially you write N, the position, in factorial positional system, and read the permutation from the result.

$$18=3110_!$$

We start

$$1234$$ $$3110$$

Pick the one at position $3$, remove the position handled and the element ($4$).

$$4$$ $$123$$ $$110$$

Pick the next one at position $1$, remove the position handled and the element ($2$).

$$42$$ $$13$$ $$10$$

Pick the next one at position $1$, remove the position handled and the element ($3$).

$$423$$ $$1$$ $$0$$

Finally take the last element to have $4231$ as expected.

(You can read the order directly. Start from the left and use order in the alphabet, if you find the same position twice, just increment it. Therefore

$3110_!$ is $3, 31, 311=312, 3120 \to 4231$

$1210_!$ would be $1,12,121=122=123,1230 \to 2341$)

$\endgroup$
1

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.