Permutational Number System

Permutational Number System^[1] or Permutadic for short is a number system based on permutations. The permutational number system is a mixed radix number system and is a generalization of the factorial number system which is primarily used for ranking (numbering) and un-ranking of k-permutations.

Any non-negative integer n can be represented in permutational number system, which is a sequence of k + 1 digits/numbers that can be converted to k-permutation of s unique elements using them as Deep code if n < ^sP_k. Deep code is a generalization of Lehmer code. In this article permutational number system of degree d is referred to as permutadic(d)

Definition

In combinatorics, permutational number system of degree d, for some positive integers s and k such that 1 ≤ k ≤ s and d = s − k, is a correspondence between natural numbers (starting from 0) and k-permutations of s items and is represented as a sequence $[C_{k - 1}, C_{k - 2}, C_{k - 3}, . . . C_{1}, C_{0}] (d)$ where $C_{i} \in ℕ$ .

Permutational number system of degree d also referred to as permutadic(d) for short, is a mixed radix number system that has a unique representation for all natural numbers. The number n corresponding to the permutadic(d) string

[C_{k - 1}, C_{k - 2}, C_{k - 3}, . . . C_{1}, C_{0}] (d)

is expressed by the equation -

n = \sum_{i = 1}^{k}^{s - i} P_{k - i} \cdot C_{k - i}

where ^sP_k is the minimum number such that, 0 ≤ n < ^sP_k and d = s − k. For a given d ≥ 0, permutadic(d) can also be defined as a mixed radix numeral system where the i^th digit from the right has the base d+1 and can be expressed by the equation -

$n = \sum_{i = 0}^{j}^{d + i} P_{i} \cdot C_{i} |^{d + j} P_{j} \leq n$

The place value ^d+iP_i for i > 0 can also be written as

\frac{(d + i)!}{d!} = (d + i) (d + i - 1) . . . (d + 1) = \prod_{j = 1}^{i} (d + j)

Place value for permutadic(d)*. Right most digit is the least significant digit*
Index	7	6	5	4	3	2	1	0
Radix/Base	d+8	d+7	d+6	d+5	d+4	d+3	d+2	d+1
Place value	^d+7P₇	^d+6P₆	^d+5P₅	^d+4P₄	^d+3P₃	^d+2P₂	^d+1P₁	^dP₀
Highest digit allowed	d+7	d+6	d+5	d+4	d+3	d+2	d+1	d

Place value for permutadic(3)*. Right most digit is the least significant digit*
Radix/Base	11	10	9	8	7	6	5	4
Place value	¹⁰P₇	⁹P₆	⁸P₅	⁷P₄	⁶P₃	⁵P₂	⁴P₁	³P₀
Place value in decimal	604800	60480	6720	840	120	20	4	1
Highest digit allowed	10	9	8	7	6	5	4	3

From this it follows that the digits allowed at index i are in range [0, d+i ]. For example, for d=2, digit allowed at 1^st index are 0,1,2 and 3 and at 2^nd index, allowed digits are 0,1,2,3 and 4. As permutadic is mixed radix based number system, hence all the properties of mixed radix number system applies to permutadic and which means a decimal number can be converted to permutadic representation by repeatedly dividing the number by the base (d+1, d+2, d+3, ...), considering remainder as digit for index starting from least significant(left most) digit.

For example, 8000₁₀ can be converted to permutadic(3) by following successive divisions:

8000 ÷ 4 = 2000, remainder 0

2000 ÷ 5 = 400, remainder 0

400 ÷ 6 = 66, remainder 4

66 ÷ 7 = 9, remainder 3

9 ÷ 8 = 1, remainder 1

1 ÷ 9 = 0, remainder 1

The process ends when the quotient reaches zero. Reading the remainders backward gives 1, 1, 3, 4, 0, 0. Hence the permutadic(3) representation of 8000₁₀ is [1, 1, 3, 4, 0, 0](3) and it can be easily verified that 1(⁸P₅) + 1(⁷P₄) + 3(⁶P₃) + 4(⁵P₂) + 0(⁴P₁) + 0(³P₀) = 8000₁₀

Application

Permutational number system has following major applications-

To rapidly compute the k-permutation from the set of s items, at a given position n in the lexicographical order (Also known as n^th k-permutation), without explicitly computing and listing down all the k-permutations preceding it. For example, if we want to find the lexicographical vigintillion-th(10⁶³) 50-permutation of 100 elements, it is not feasible to compute it sequentially. Whereas, converting 10⁶³ to permutadic(100-50) and then converting permutadic to desired permutation can be done in a fraction of a second.
To compute the lexicographical rank the given k-permutation, using Deep code encoding. This is similar to computing the rank of unique permutation using factorial number system and Lehmer code encoding. For example, if we have a k-permutation of s elements, it can be converted to permutadic(s-k) using Deep code encoding and then permutadic can be converted to a decimal number as a solution.
Permutadic can also be used to randomly generate k-permutations of a given set of elements.
Permutational Number system along with Deep-code can be used to encode text to numbers.
It can be used in scheduling applications. For example to create efficient and optimized timetables.

Example

Integer 8000 as permutadic(4) string

Integer 8000 can be represented in permutadic(4) as [4,6,0,4,0](4) because $4 (^{8} P_{4}) + 6 (^{7} P_{3}) + 0 (^{6} P_{2}) + 4 (^{5} P_{1}) + 0 (^{4} P_{0}) = 8000$

Permutadic(4) representation of integers from 0 to 99
Decimal	Permutadic	Decimal	Permutadic	Decimal	Permutadic	Decimal	Permutadic	Decimal	Permutadic
0	[0](4)	20	[4,0](4)	40	[1,2,0](4)	60	[2,0,0](4)	80	[2,4,0](4)
1	[1](4)	21	[4,1](4)	41	[1,2,1](4)	61	[2,0,1](4)	81	[2,4,1](4)
2	[2](4)	22	[4,2](4)	42	[1,2,2](4)	62	[2,0,2](4)	82	[2,4,2](4)
3	[3](4)	23	[4,3](4)	43	[1,2,3](4)	63	[2,0,3](4)	83	[2,4,3](4)
4	[4](4)	24	[4,4](4)	44	[1,2,4](4)	64	[2,0,4](4)	84	[2,4,4](4)
5	[1,0](4)	25	[5,0](4)	45	[1,3,0](4)	65	[2,1,0](4)	85	[2,5,0](4)
6	[1,1](4)	26	[5,1](4)	46	[1,3,1](4)	66	[2,1,1](4)	86	[2,5,1](4)
7	[1,2](4)	27	[5,2](4)	47	[1,3,2](4)	67	[2,1,2](4)	87	[2,5,2](4)
8	[1,3](4)	28	[5,3](4)	48	[1,3,3](4)	68	[2,1,3](4)	88	[2,5,3](4)
9	[1,4](4)	29	[5,4](4)	49	[1,3,4](4)	69	[2,1,4](4)	89	[2,5,4](4)
10	[2,0](4)	30	[1,0,0](4)	50	[1,4,0](4)	70	[2,2,0](4)	90	[3,0,0](4)
11	[2,1](4)	31	[1,0,1](4)	51	[1,4,1](4)	71	[2,2,1](4)	91	[3,0,1](4)
12	[2,2](4)	32	[1,0,2](4)	52	[1,4,2](4)	72	[2,2,2](4)	92	[3,0,2](4)
13	[2,3](4)	33	[1,0,3](4)	53	[1,4,3](4)	73	[2,2,3](4)	93	[3,0,3](4)
14	[2,4](4)	34	[1,0,4](4)	54	[1,4,4](4)	74	[2,2,4](4)	94	[3,0,4](4)
15	[3,0](4)	35	[1,1,0](4)	55	[1,5,0](4)	75	[2,3,0](4)	95	[3,1,0](4)
16	[3,1](4)	36	[1,1,1](4)	56	[1,5,1](4)	76	[2,3,1](4)	96	[3,1,1](4)
17	[3,2](4)	37	[1,1,2](4)	57	[1,5,2](4)	77	[2,3,2](4)	97	[3,1,2](4)
18	[3,3](4)	38	[1,1,3](4)	58	[1,5,3](4)	78	[2,3,3](4)	98	[3,1,3](4)
19	[3,4](4)	39	[1,1,4](4)	59	[1,5,4](4)	79	[2,3,4](4)	99	[3,1,4](4)

Comparison with other combinatoric number systems

Number system	Width	Has Degree	Primary use
Combinatorial number system^[2]	fixed width	yes	Compute n^th combination
Factorial number system^[3]	variable width	no	Compute n^th unique permutation using Lehmer code
Permutational number system	variable width	yes	Compute n^th k-permutation using Deep code

Conversion from decimal to permutadic

Algorithm

To convert the decimal to permutadic representation we do not need to explicitly calculate the multipliers ^sP_k for the permutadic digits. The reason is that the place value for least significant digit in permutational number system is always ^s-kP₀ = 1 and the next place value can be calculated by increasing the divisor because ^sP_k = s ⋅ ^s-1P_k-1 and hence the place value for second least significant digit can be calculated as -

< s u p > d + 1 < / s u p > P < s u b > 1 < / s u b > = (d + 1) (< s u p > d < / s u p > P < s u b > 0 < / s u b >) = d + 1

And in general place value for the i^th digit can be calculated as -

$< s u p > d + i < / s u p > P < s u b > i < / s u b > = (d + i) (< s u p > d + i - 1 < / s u p > P < s u b > i - 1 < / s u b >)$

Following algorithm^[4] converts the decimal number to permutadic string. Least significant digit will be stored at the 0^th index of a list.

public static List<Integer> toPermutadic(int decimalValue, int degree) {
    List<Integer> permutadicValues = new ArrayList<>();
    ++degree;
    do  {
        permutadicValues.add(decimalValue % degree);
        decimalValue = decimalValue / degree;
        degree++;
    }while(decimalValue > 0);
    return permutadicValues;
}

Example

Converting 7000 to permutadic of degree 4
N	Divisor	Quotient	Remainder
7000	degree + 1 = 5	1400	0
1400	6	233	2
233	7	33	2
33	8	4	1
4	9	0	4
Result = [4,1,2,2,0](4)

It can be easily verified that 4(⁸P₄) + 1(⁷P₃) + 2(⁶P₂) + 2(⁵P₁) + 0(⁴P₀) = 7000

Conversion from permutadic to decimal

Algorithm

For conversion from permutadic string to decimal, we do not need to calculate the place value for each digit explicitly. Start with the least significant digit for which place value is always 1 and calculate the place value for remaining digits from relationship ^sP_k = s ⋅ ^s-1P_k-1 for successive digits. Following algorithm converts permutadic string using this approach.

public static long toDecimal(List<Integer> permutadicValues, int degree) {
    long sum = 0;
    long placeValue = 1;

    for(Integer permutadicDigit : permutadicValues) {
        sum  = sum + ( placeValue * permutadicDigit );
        placeValue = placeValue * (++degree );
    }
    return sum;
}

Example

Converting permutadic(4) string 4,1,2,2,0 to decimal
Permutadic digit (starting from least significant)	degree	placeValue= placeValue+(digit x degree)	sum = sum + ( placeValue x digit )
0	4	1	0
2	5	5	10
2	6	30	70
1	7	210	280
4	8	1680	7000

Relationship with k-permutation

There is a natural mapping between the integers 0, ..., ^sP_k -1 and k-permutation of s elements in lexicographical order, when the integers are expressed in permutadic(s-k) form. This mapping has been termed as Deep code which is a generalization of Lehmer code. For example, with s = 5 and k = 3, such a mapping is

decimal	permutadic(3)	3-permutation of 5 elements (0,1,2,3,4)
0₁₀	[0](3)	[0, 1]
1₁₀	[1](3)	[0, 2]
2₁₀	[2](3)	[0, 3]
3₁₀	[3](3)	[0, 4]
4₁₀	[1,0](3)	[1, 0]
5₁₀	[1,1](3)	[1, 2]
₆₁₀	[1,2](3)	[1, 3]
₇₁₀	[1,3](3)	[1, 4]
₈₁₀	[2,0](3)	[2, 0]
9₁₀	[2,1](3)	[2, 1]
10₁₀	[2,2](3)	[2, 3]
11₁₀	[2,3](3)	[2, 4]
12₁₀	[3,0](3)	[3, 0]
13₁₀	[3,1](3)	[3, 1]
14₁₀	[3,2](3)	[3, 2]
15₁₀	[3,3](3)	[3, 4]
16₁₀	[4,0](3)	[4, 0]
17₁₀	[4,1](3)	[4, 1]
18₁₀	[4,2](3)	[4, 2]
19₁₀	[4,3](3)	[4, 3]

In each case, to calculate the k-permutation start with the leftmost permutadic digit (here, 0, 1, 2 or 3) as the first permutation digit, then removing it from the ordered list of all s elements (0, 1, 2, 3, 4 and 5 in this case). Consider this list of s items as zero index based and use each successive permutadic digit to choose from its remaining elements. If the second permutadic digit is "0" then the 0^th element of the list is selected for the second permutation digit and is then removed from the list. Similarly, if the second permutadic digit is "1", then element at first index is selected and then removed. This process is continued k times.

To make it more clear let's take an example. Say we need to find out the 2000^th 4-permutation of 10 elements. First, calculate the permutadic(10-4) equivalent of 2000 as [3,8,5,5](6) and create an ordered list "L" of 10 items, say (0,1,2,3,4,5,6,7,8,9). Now starting with the most significant digit (3 in this case), use it as an index to select and remove the items from the list L will generate a new list (3, 9, 6, 7) of selected items which is the desired 2000^th 4-permutation of 10 elements.

decimal: 2000   ─► permutadic(6):[3, 8, 5, 5](6) ─►  [3, 9, 6, 7]
permutadic:     3                    :   8                  :   5                :   5   
                ├─┬─┬─┐                  ├─┬─┬─┬─┬─┬─┬─┬─┐      ├─┬─┬─┬─┬─┐          ├─┬─┬─┬─┬─┐
set :          (0,1,2,3,4,5,6,7,8,9) ─► (0,1,2,4,5,6,7,8,9) ─► (0,1,2,4,5,6,7,8) ─► (0,1,2,4,5,7,8)
                      │                                  │                │                    │    
2000th permutation:  (3,                                 9,               6,                   7)

Comparison with factorial number system

Factoradic is a special case of permutadic(d) when d = 0. This is because of the fact that for permutadic(0), place value ^d+iP_i at index i is $i P_{i} = \frac{i!}{0!} = i!$ which is the same as a place value in factorial number system. From this it follows that permutadic of degree 0 is same as factoradic.

Decimal	Permutadic(0)	Factoradic
1000	[1, 2, 1, 2, 2, 0, 0](0)	[1, 2, 1, 2, 2, 0, 0]
2000	[2, 4, 3, 1, 1, 0, 0](0)	[2, 4, 3, 1, 1, 0, 0]
3000	[4, 1, 0, 0, 0, 0, 0](0)	[4, 1, 0, 0, 0, 0, 0]

References

↑ Patel, Deepesh (27 July 2022). "Generating the nth Lexicographical Element of a Mathematical k-Permutation using Permutational Number System". Applied Computing eJournal. 5 (116). SSRN 4174035 Check |ssrn= value (help) – via SSRN.
↑ McCaffrey, James (July 2004). "Generating the mth Lexicographical Element of a Mathematical Combination". MSDN. 790 – via Microsoft.
↑ Knuth, Donald (December 2021). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. ISBN 9780201038064. Search this book on
↑ Patel, Deepesh (2022-10-07), JNumberTools V1.0.0, retrieved 2022-12-04

External links

Online Calculator: Combination By Lexicographical Index This calculator generates nth combination.
Online Calculator: Combinatorial number system This online calculator converts natural number to a sequences of k-combinations, referred as the combinatorial number system of degree k (for some positive integer k)
Online Calculator: Factorial Number System
Lehmer code Generator Generates lehmer code for a given permutation.

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.

[1] Patel, Deepesh (27 July 2022). "Generating the nth Lexicographical Element of a Mathematical k-Permutation using Permutational Number System". Applied Computing eJournal. 5 (116). SSRN 4174035 Check |ssrn= value (help) – via SSRN.

[2] McCaffrey, James (July 2004). "Generating the mth Lexicographical Element of a Mathematical Combination". MSDN. 790 – via Microsoft.

[3] Knuth, Donald (December 2021). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. ISBN 9780201038064. Search this book on

[4] Patel, Deepesh (2022-10-07), JNumberTools V1.0.0, retrieved 2022-12-04

[1]

[2]

[3]

[4]

Permutational Number System

Contents

Definition

Application

Example

Integer 8000 as permutadic(4) string

Comparison with other combinatoric number systems

Conversion from decimal to permutadic

Algorithm

Example

Conversion from permutadic to decimal

Algorithm

Example

Relationship with k-permutation

Comparison with factorial number system

See Also

References

External links