0
$\begingroup$

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$.

Suppose if $n=4$, the possible permutations with their labels are,

0:  1234
1:  1243
2:  1324
3:  1342
4:  1432
5:  1423
6:  2134
7:  2143
8:  2314
9:  2341
10: 2431
11: 2413
12: 3214
13: 3241
14: 3124
15: 3142
16: 3412
17: 3421
18: 4231
19: 4213
20: 4321
21: 4312
22: 4132
23: 4123

With any well defined labelling scheme, given a number $m, 0 \leq m < n!$, we can get back the permutation sequence. Further, these labels can be normalised to be between $0$ and $1$. The above labels can be transformed into,

0:       1234
0.0434:  1243
0.0869:  1324
0.1304:  1342
0.1739:  1432
0.2173:  1423
0.2608:  2134
0.3043:  2143
0.3478:  2314
0.3913:  2341
0.4347:  2431
0.4782:  2413
0.5217:  3214
0.5652:  3241
0.6086:  3124
0.6521:  3142
0.6956:  3412
0.7391:  3421
0.7826:  4231
0.8260:  4213
0.8695:  4321
0.9130:  4312
0.9565:  4132
1:       4123

Now, given $n$ and $m^{th}$ normalised label, can we get the $m^{th}$ permutation while avoiding the expansion of $n!$ ? For example, in the above set of permutations, if we were given the $m^{th}$ normalised label to be $0.9$, is it possible to get the closest sequence 4312 as the answer without computing $4!$ ?

Math SE crosspost

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Divide the interval $[0,1]$ in $n$ parts of the same length. The part into which the label falls gives you the first element of the permutation. Then divide the part into $n-1$ parts of the same length. The label is in one of them, which will tell you the next element of the permutation. You can continue in this way. However, I am not sure what counts as 'without computing $n!$'. $\endgroup$ – NotDijkstra Jul 3 '20 at 18:29
  • $\begingroup$ Yeah, I think that could work. Just trying to avoid blown up values of $n!$ as $n$ gets larger but at the same time I am trying to have an efficient algorithm to generate the sequence. $\endgroup$ – Ganesh Jul 3 '20 at 19:07
  • $\begingroup$ The interesting part is determining the next digit from the chosen subinterval. This depends on the specific order in which you are listing the permutations. What order is that? $\endgroup$ – NotDijkstra Jul 3 '20 at 19:20
  • $\begingroup$ Yeah, good question. I would prefer using the lexicographic/sorted order here. For example, 1234 would come before 1243. I think I have mentioned them in that order in the example provided in the question. $\endgroup$ – Ganesh Jul 3 '20 at 19:26
  • 1
    $\begingroup$ Not exactly. Binary search will not be necessary, and in the second step it is not $[0,1]$ what needs to be divided into $n-1$ parts, but the previously selected subinterval. Maybe let me write it all. $\endgroup$ – NotDijkstra Jul 3 '20 at 19:38
0
$\begingroup$

Well, from the clarifications made in the comments, then this could be a solution.

I haven't checked for correctness. Specifically the requirement of choosing the closest label to the one input. I think I am taking the one immediately below the number input. Probably that can be fixed by using closest integer, instead of floor below.

Let $L=L_1$ be the input label, which is a real number. Maybe we can just assume that it is in $[0,1]$.

We begin with the full collection of numbers say $C_1=\{1,2,3,...,n\}$ from where one will be eliminated at each step.

In the first step we compute $a_1=\lfloor L_1\cdot n\rfloor$. We pick the $a_1$-th element $p_1$ of $C_1$ to be the first element of the permutation and remove it form $C_1$. So, define $C_2=C_1\setminus\{p_1\}$. Define $L_2=L_1\cdot n-a_1$.

Continue in this way, in the $k$-th step, for $k=2,3,...,n$, put $a_k=\lfloor L_k\cdot (n-k+1)\rfloor$, take $p_k$ to be the $a_k$-th element of $C_k$ and define $C_{k+1}=C_k\setminus\{p_k\}$ and $L_{k+1}=L_k\cdot(n-k+1)-a_k$.

Finish when there are no more elements in $C_k$, or maybe when there is just one which will be forced to be the last element in the permutation.

See also factorial number system. Since this is essentially what we are doing.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! It's a great solution. I'm just going to go a bit off topic here - is it possible to tweak the algorithm to work in a multi-threaded environment? $\endgroup$ – Ganesh Jul 3 '20 at 21:21
  • $\begingroup$ @Ganesh I am not a programmer or computer scientist. So, I don't really know. I suppose that if $L$ and $n$ have many digits, then the algorithms for fast multiplication should admit some parallelization. So, the multiplications above could benefit from it. I don't know if it is possible to do something with the rest of the work needed to determine $p_1,p_2,...p_n$. $\endgroup$ – NotDijkstra Jul 3 '20 at 21:59
  • $\begingroup$ No, worries. Thanks a lot for the answer. I wish to mark this as the accepted answer but I don't have too many points. $\endgroup$ – Ganesh Jul 6 '20 at 4:23
  • $\begingroup$ It is a bit confusing to understand a mixed radix system. Is it possible to figure out the index of element $p_k$ in $C_1$ in the $k^{th}$ step without removing $p_1$, $p_2$, ..., $p_{k-1}$ elements from $C_1$ in the previous steps? $\endgroup$ – Ganesh Jul 14 '20 at 16:09

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.