Nth K-Permutation

---

In combinatorics, generating N^th k-Permutation directly without explicitly computing/generating and listing down all the preceding k-permutations is important because number of permutations are astronomical for sets of larger size. Total number of k-permutations for a set of size S is ^sP_k = S!/(S-k)!. For s=100 and k=50, ^sP_k = ¹⁰⁰P₅₀ = 3.068518756 x 10⁹³. For such a big number generating all permutations might take months which is not practical. N^th k-permutation algorithm provides the mean to generate directly the N^th permutation. There can be 2 ways we can define the Nth k-permutation.

1. In lexicographical order of permutation and
2. In Combination order. That is, in lexicographical order of combinations in the permutation sequence, i.e, first generating all the permutations for a first combination before generating permutations of next possible combination.

Generating N^th k-Permutation in lexicographic order

This can be achieved by using a Permutational number system, which is a generalised form of Factorial number system, and is introduced in [| JNumberTools], an open source combinatorics library by [| Deepesh Patel]. It is also known as Permutadic for short.

Description

To generate the N^th k-permutation of set of size S, using permutadic, first convert the number to equivalent permutadic string and then find the correct mapping between the permutadic digits and the list of numbers from 0 to S. Mapping process start by using the leftmost permutadic digit and then removing the numbers from a list at a given index.

Example

Suppose we need to find the 5050^th 5-permutation of 8 digits. First we convert 5050 to permutadic, which will result in a sequence [6, 0, 0, 2, 2] so from our set of 8 digits [0, 1, 2, 3, 4, 5, 6, 7] we first remove the value at 6^th index which is 6. After this the remaining permutadic digits will be [6, 0, 0, 2, 2] and the list will be [0, 1, 2, 3, 4, 5, 7]. Continue this process and the sequence of digits obtained will be the 5050^th permutation (starting from 0). The complete calculation is illustrated in the table below.

Permutadic	List containing remaining numbers	index	value removed at a index	Sequence Formed
[6, 0, 0, 2, 2]	[0, 1, 2, 3, 4, 5, 6, 7]	6	6	[6]
[6, 0, 0, 2, 2]	[0, 1, 2, 3, 4, 5, 7]	0	0	[6, 0]
[6, 0, 0, 2, 2]	[1, 2, 3, 4, 5, 7]	0	1	[6, 0, 1]
[6, 0, 0, 2, 2]	[2, 3, 4, 5, 7]	2	3	[6, 0, 1, 3]
[6, 0, 0, 2, 2]	[2, 4, 5, 7]	2	5	[6, 0, 1, 3, 5]

Algorithm

In actual implementation finding the permutadic and mapping it to corresponding Nth k-permutation, both these steps can be clubbed together for optimisation and the below mentioned algorithm is doing the same.

Given:

• s = total number of items.
• n = positive integer to jump to
• k = size of permutation (0<=k<=S)
• L = list of numbers containing numbers 0, 1, 2.. k-1
• O=initially empty output list

Algorithm Steps:

1. compute max_allowed = ^sP_k
2. If n > ^sP_k return. //k-permutation does not contain n^th digit. out of reach
3. compute divisor = ^s-1P_k-1
4. compute next = n-1
5. for i = 1 to k
   1. C_k-i = N/divisor //calculating permutadic digit
   2. N = N mod divisor
   3. divisor = divisor / next
   4. next = next -1
   5. O[i-1] = L[C_k-i ] //finding corresponding mapping in the same loop
6. return O

Generating N^th k-Permutation in combination order

Background

Knowledge of following topics is necessary to understand below mentioned algorithm:

• Factorial number system:

• Combinatorial number system:

• k-permutation generation: k-permutation is a set of all unique permutations of size k where 0<=k<=S, where S is the number of items. Finding k-permutations is a 2 step algorithm-

1. Find all combinations of size k in lex order(using standard algorithm for unique combinations)
2. For all combinations in step 1, find all k! unique permutations in lex order.

Algorithm description

Suppose we need to find out the N^th k-permutation instead of N^th unique permutation, in lexicographical order. Factorial-Number-System clearly will not be able to generate the correct values for N > ^sC_k as after ^sC_k permutations, the sequence will change and start with next unique combination). The solution lies in the algorithm to generate k-permutations in lexicographical order. In step2 of k-permutation we generate unique-permutations, and hence Factorial-Number-System will work correctly to find out N^th value if N < k!. Now suppose our value is slightly greater than k! but less than 2*k! ( N> k! and N < 2*k!).

What we can do in this case? We already know the number of permutations in step 2 is k! , So clearly we can jump to next combination say C₁ (assuming 0 based index) via combinadic and then use the factorial-number-system starting from C₁ to find the (N-k!)^th, value using factorial-number-system. That is taking C₁ as 0^th permutation and finding the (N-k!)^th permutation which is a desired permutation. Now take another example. where N > J * k! and N< ^sP_k where J is any positive integer. Know we know that -

• Size of sequential permutations in step 2 above, for each combination from step 1 is k!

• We can jump to any combination say M^th combination via Combinatorial-Number-System in lexicographical order because we also know the number of combinations is ^sC_k.
• From above information we can first find J = N/k!. This will give us the correct combination number to jump to, which we can then reach via Combinatorial-Number-System. Then we will find the correct value of permutation via modulo division and then jump to the desired permutation number, taking the latest combination as starting point via Factorial-Number-System and corresponding Lehmer-code.

Algorithm

Given:

• S = Total number of items.
• N = positive integer to jump to
• K = size of permutation (0<=k<=S)

Algorithm Steps:

1. Let I = N (positive integer to jump to)
2. Let J = no. of permutation for a given C = ^sP_k/ ^sC_k = k!
3. For I = N, step N, till I < ^sP_k repeat step 4-7
4. Let C-skip = I/J
5. Let P-skip = I mod J
6. Use Combinatorial-Number-System to generate C-skip^th combination starting from 0^th permutation. You can also use Gosper's hack instead of standard algorithm if the number of bits in 'int' variable is sufficient ( >=S)
7. N^th k-permutation = Find P-skip^th permutation by using factoradic and corresponding Lehmer code ( taking C-skip^th combination from step 6 as 0^th permutation).

References

This article "Nth K-Permutation" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Nth K-Permutation. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Combinatorial hierarchy
• Ideal ring bundle
• Lattice ball
• Permutational number system

---