Permutational number system

---

Permutational-Number-System or Permutadic is a number system based on permutations. It is first introduces by Deepesh Patel in JNumberTools, an open source combinatorics library where it is used to find the next N^th k-permutation in lexicographic order.

In combinatorics, Permutational-number-system of size s and degree k,( for some positive integers k and s where $k\leqslant s$), also referred to as Permutadic or the Deep's representation of an integer, is a correspondence between natural numbers (starting from 0) N and k-permutations, represented as sequence [C_k-1, C_k-2.. C₁, C₀ ][s, k] where $s>Ci\geqslant 0$. Since it is a string of numbers, we can interpret this as a type of number system for representing N.

The number N corresponding to (c_k-1, ..., c₁, c₀) is given by -

$N={\biggl [}\,^{s-1}P_{k-1}*C_{k-1}{\biggr ]}+{\biggl [}\,^{s-2}P_{k-2}*C_{k-2}{\biggr ]}+\cdots +{\biggl [}\,^{s-k+1}P_{1}*C_{1}{\biggr ]}+{\biggl [}\,^{s-k}P_{0}*C_{0}{\biggr ]}$

or

$N=\sum _{i=1}^{i=k}\,^{s-i}P_{k-i}*C_{k-i}$

where, $^{s}P_{k}=s!\div (s-k)!$

for k=s, the representation is same as in case of Factorial number system, which implies that the factorial-number-system is a special case of permutational-number-system where degree of permutational-number-system( denoted by k) is equal to size(denoted by s) of the permutational-number-system.

Application

Permutational number system allows quick computation of the k-permutation of set of s items, at a given position in the lexicographical order, without explicitly computing and listing down all the k-permutations preceding it. This can be used to randomly generate k-permutations of a given set.

Algorithm

Algorithm details

To compute the permutadic of a natural number N divide the number by ^s-1P_k-1 and store the quotient. This is the most significant value of permutadic representation of N. To find the next value, repeat the process by dividing remainder of the result by ^s-2P_k-2 and continue the process of storing the quotient and dividing the remainder by ^n-iP_k-i till $i\leqslant k$. Note that if you know ^sP_k you do not need to calculate ^s-1P_k-1 from scratch because ^s-1P_k-1 can be computed as $^{n-1}P_{k-1}=\,^{n}P_{k}/n$ this shortcut to calculate ^s-1P_k-1 when ^sP_k is given is used in the below mentioned algorithm

Algorithm steps

1. Input: N = natural number, s = size of permutadic and and k= degree of permutadic
2. compute divisor = ^s-1P_k-1
3. compute next = n-1
4. for i = 1 to k
   1. C_k-i = N/divisor
   2. N = N mod divisor
   3. divisor = divisor / next
   4. next = next -1
5. return C

• Note: To make the algorithm work for s=k to generate factorial-number-system, we need to put a check in step 4.4 in above algorithm to not decrement the value of variable 'next' if it is 1 to avoid the divide by zero error

Example

Suppose we need to find the permutadic of 5050 for size 8 and degree 5. For this first compute ⁷P₄ = 840 and divide 5050 by 840 which gives us quotient 6 and remainder 10. Now to compute next permutation that is ⁶P₃ simply compute 840/7 = 120. Repeat the entire process as in below table and store the quotient values which will result in the [6,0,0,2,2] so the permutational-number-system equivalent of 5050 of degree 5 and size 8 will be [6,0,0,2,2][8,5]. Note that degree (5 in this example) is not required in the permutational-number-system representation as it can be calculated from the size of the array.

Conversion of 5050 to permutadic of size 8 and degree 5

N	Divisor	Quotient	Remainder
5050	7P4 = 840	5050/840 = 6	10
10	6P3 = 840/7 =120	10/120 = 0	10
10	5P2 =120/6 = 20	10/20 = 0	10
10	4P1 = 20/5 = 4	10/4 = 2	2
2	3P0 = 4/4 = 1	2/1 = 2	0

Conversion to decimal

To convert permutational-number back to decimal, reverse the process and multiply each C_i in permutadic by ^s-k+iP_i and add the result. Following table shows the example of converting [6,0,0,2,2][8,5] to decimal equivalent.

Conversion of permutadic [6,0,0,2,2][8,5] to decimal equivalent

Permutadic digit	Multiplier	Result	Cumulative Sum
6	7P4 = 840	6 x 840 = 5040	5040
0	6P3 = 840/7 =120	0 x 120 = 0	5040 + 0 = 5040
0	5P2 = 120/6 = 20	0 x 20 = 0	5040 + 0 = 5040
2	4P1 = 20/5 = 4	2 x 4 = 8	5040 + 8 = 5048
2	3P0 = 4/4 = 1	2 x 1 = 2	5048 + 2 = 5050

Finding N^th k-permutation

To find the N^th k-permutation first convert N to permutadic and create a list containing numbers from 0 to N-1 in order. Then read the permutadic values starting from most significant value till least significant and get the value from the list at index C_i. The resultant sequence of numbers will be the N^th k-permutation starting from 0.

References

This article "Permutational number system" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Permutational number system. 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)

• Lattice ball
• Combinatorial hierarchy
• Ideal ring bundle
• Nth K-Permutation

---