How to iterate over all permutations and about factorial decomposition of natural numbers
Problems about the enumeration of all possible permutations of a given set of entities arise in programming quite often. As is known from combinatorics, the number of possible permutations of n objects is simply the factorial of n
Factorial is a fairly fast growing function, its asymptotics (Stirling formula) speaks about it, although it suffices to look at the factorials of the first few members of the natural series:
As you can see, the factorial of 13 already does not fit into the long data type.
')
If we aim to find a one-to-one correspondence between the number of the permutation — a number in the range from 1 to n ! - and its implementation, you can come across one very interesting mathematical fact.
First, let us recall the concept of a positional number system. The contribution of each digit of the number to its value in the positional system at the base of K is the digit multiplied by the base of K to a degree equal to the position of the discharge in the number record. The base of the number system is usually written as a subscript, thus
The positional record, in addition to compactness, has the invaluable property that the algorithm for performing arithmetic operations turns out to be extremely simple (there is a historical tale that in medieval schools the study of arithmetic took several years, because calculations over numbers in the nonpositional Roman notation had many rules to conduct simple addition!)
It turns out that there is, and there is an unambiguous, decomposition and a way to write a number, in which each digit in such a representation is multiplied by the FACTORIAL of the position number.
Let's show it on examples:
In a conventional positional system, the value of each digit must be strictly less than the base. In the factorial system, however, each “bit” is less than or equal to the base of the factorial before which it stands. At the same time, the usual rules for the addition of discharge transfer during overflow apply.
More mathematically strictly: each positive integer n can be uniquely represented as the following sum:
Where
k m <= m - coefficient when m! - it is the digit of the number in its factorial representation,
p - the number of "bits" in the number in its factorial representation
that is, the number is written as k p k p-1 k p-2 ... k 2 k 1
We now describe how to use the factorial representation (decomposition) of a number to generate the corresponding permutation. We arrange n elements in ascending order of the index from 1 to n. For each number in the range 0..n! -1, we make a factorial decomposition by calculating its coefficients k m . In the zero expansion, the coefficients k m will be all zeros, in the expansion of the number n! -1, all k m = m, m varies in the range from 0 to n-1. Now we will place the element with the number m in the place with the number k m +1, counting only the free places left to this step. In fact, this procedure repeats the arguments that are given when calculating the number of possible permutations of n elements - the first element can be placed in n ways, the second - (n-1) method, and so on. Thus, we obtain all possible permutations of n distinct elements.
We illustrate this for 5 items (120 permutations) and permutation No. 77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!
Not being a practical programmer, I still make assumptions (theoretical)), how could such a decomposition be used. You can divide the total number of possible permutations into subranges by the number of parallel execution threads available, and extract the current permutation directly from the representation of the loop variable in the factorial record. Decomposition into a factorial form is a computationally complicated task, but you can decompose only the starting number of the subrange and then simply add one, transferring it to the next digit in case of overflow.
n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
Factorial is a fairly fast growing function, its asymptotics (Stirling formula) speaks about it, although it suffices to look at the factorials of the first few members of the natural series:
one! one
2! 2
3! 6
four! 24
five! 120
6! 720
7! 5,040
eight! 40 320
9! 362 880
ten! 3,628,800
eleven! 39,916,800
12! 479 001 600
13! 6,227,020,800
14! 87 178 291 200
15! 1 307 674 368 000
As you can see, the factorial of 13 already does not fit into the long data type.
')
If we aim to find a one-to-one correspondence between the number of the permutation — a number in the range from 1 to n ! - and its implementation, you can come across one very interesting mathematical fact.
First, let us recall the concept of a positional number system. The contribution of each digit of the number to its value in the positional system at the base of K is the digit multiplied by the base of K to a degree equal to the position of the discharge in the number record. The base of the number system is usually written as a subscript, thus
1966 10 = 1 * 10 3 + 9 * 10 2 + 6 * 10 1 + 6 (* 10 0 )
10110001 2 = 1 * 2 7 + 0 * 2 6 + 1 * 2 5 + 1 * 2 4 + 0 * 2 3 + 0 * 2 2 + 0 * 2 1 + 1 * 2 0 (= 177 10 )
The positional record, in addition to compactness, has the invaluable property that the algorithm for performing arithmetic operations turns out to be extremely simple (there is a historical tale that in medieval schools the study of arithmetic took several years, because calculations over numbers in the nonpositional Roman notation had many rules to conduct simple addition!)
It turns out that there is, and there is an unambiguous, decomposition and a way to write a number, in which each digit in such a representation is multiplied by the FACTORIAL of the position number.
Let's show it on examples:
1985 = 2 * 6! + 4 * 5! + 2 * 4! + 2 * 3! + 2 * 2! + 1 * 1!
2 940 861 129 405 = 2 * 15! + 3 * 14! + 10 * 13! + 3 * 12! + 6 * 11! + 8 * 10! + 4 * 9! + 8 * 8! + 0 * 7! + 2 * 6! + 2 * 5! + 1 * 4! + 3 * 3! + 1 * 2! + 1 * 1!
In a conventional positional system, the value of each digit must be strictly less than the base. In the factorial system, however, each “bit” is less than or equal to the base of the factorial before which it stands. At the same time, the usual rules for the addition of discharge transfer during overflow apply.
More mathematically strictly: each positive integer n can be uniquely represented as the following sum:
Where
k m <= m - coefficient when m! - it is the digit of the number in its factorial representation,
p - the number of "bits" in the number in its factorial representation
that is, the number is written as k p k p-1 k p-2 ... k 2 k 1
We now describe how to use the factorial representation (decomposition) of a number to generate the corresponding permutation. We arrange n elements in ascending order of the index from 1 to n. For each number in the range 0..n! -1, we make a factorial decomposition by calculating its coefficients k m . In the zero expansion, the coefficients k m will be all zeros, in the expansion of the number n! -1, all k m = m, m varies in the range from 0 to n-1. Now we will place the element with the number m in the place with the number k m +1, counting only the free places left to this step. In fact, this procedure repeats the arguments that are given when calculating the number of possible permutations of n elements - the first element can be placed in n ways, the second - (n-1) method, and so on. Thus, we obtain all possible permutations of n distinct elements.
We illustrate this for 5 items (120 permutations) and permutation No. 77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!
Not being a practical programmer, I still make assumptions (theoretical)), how could such a decomposition be used. You can divide the total number of possible permutations into subranges by the number of parallel execution threads available, and extract the current permutation directly from the representation of the loop variable in the factorial record. Decomposition into a factorial form is a computationally complicated task, but you can decompose only the starting number of the subrange and then simply add one, transferring it to the next digit in case of overflow.
Source: https://habr.com/ru/post/319696/
All Articles