January 17, 2017 at 01:46How to sort through all permutations about the factorial decomposition of natural numbers
Problems of enumerating 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 rather rapidly growing function, its asymptotics (Stirling's formula) speaks about this, although it suffices to look at the factorials of the first few terms of the natural series:
As you can see, the factorial of 13 no longer fits in the data type long.
If you set yourself the goal of finding a one-to-one correspondence between a permutation number — a number in the range from 1 to n ! - and its implementation, one can come across one very interesting mathematical fact.
To begin with, we recall the concept of a positional number system. The contribution of each digit of a number to its value in a positional system at the base of K is the discharge multiplied by the base of K to the degree equal to the position of the discharge in the record of the number. The base of the number system is usually written as a subscript, thus
In addition to compactness, positional recording has the invaluable property that the algorithm for performing arithmetic operations turns out to be extremely simple (there is a historical story that it took several years to study arithmetic in medieval schools, since calculations on numbers in a non-positional Roman notation had many rules in order to conduct simple addition!)
It turns out that the decomposition and the way of writing a number exists in which the number in which each digit in this representation is multiplied by FACTORIAL is unique. item numbers.
We show this with examples:
In a conventional positional system, the value of each digit should be strictly less than the base. In a factorial system, each “rank” is less than or equal to the base of the factorial that it faces. In this case, the rules for transferring discharge during overflow that are usual for addition are valid.
More mathematically rigorous: each natural number n can be uniquely represented as the following sum:
where
k m <= m is the coefficient for m! - it’s the category of the number in its factorial representation,
p is 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
Now we describe how to use the factorial representation ( expansion) of the number to generate the corresponding permutation. Arrange n elements in increasing order of the index from 1 to n. For each number in the range 0..n! -1, we perform a factorial expansion, calculating its coefficients k m . In the expansion of zero, 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 place the element with the number m in place with the number k m +1, counting only the free places remaining 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 in (n-1) way, and so on. Thus, we get all possible permutations of n mismatched elements.
We illustrate this for 5 subjects (120 permutations) and permutations No.
77 77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!
Not being a practical programmer, I will nevertheless make assumptions (theoretical)) how such decomposition could be used. You can divide the total number of possible permutations into subbands 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. Factorial decomposition 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 rather rapidly growing function, its asymptotics (Stirling's formula) speaks about this, although it suffices to look at the factorials of the first few terms of the natural series:
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 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 no longer fits in the data type long.
If you set yourself the goal of finding a one-to-one correspondence between a permutation number — a number in the range from 1 to n ! - and its implementation, one can come across one very interesting mathematical fact.
To begin with, we recall the concept of a positional number system. The contribution of each digit of a number to its value in a positional system at the base of K is the discharge multiplied by the base of K to the degree equal to the position of the discharge in the record of the number. 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 )
In addition to compactness, positional recording has the invaluable property that the algorithm for performing arithmetic operations turns out to be extremely simple (there is a historical story that it took several years to study arithmetic in medieval schools, since calculations on numbers in a non-positional Roman notation had many rules in order to conduct simple addition!)
It turns out that the decomposition and the way of writing a number exists in which the number in which each digit in this representation is multiplied by FACTORIAL is unique. item numbers.
We show this with 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 should be strictly less than the base. In a factorial system, each “rank” is less than or equal to the base of the factorial that it faces. In this case, the rules for transferring discharge during overflow that are usual for addition are valid.
More mathematically rigorous: each natural number n can be uniquely represented as the following sum:
where
k m <= m is the coefficient for m! - it’s the category of the number in its factorial representation,
p is 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
Now we describe how to use the factorial representation ( expansion) of the number to generate the corresponding permutation. Arrange n elements in increasing order of the index from 1 to n. For each number in the range 0..n! -1, we perform a factorial expansion, calculating its coefficients k m . In the expansion of zero, 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 place the element with the number m in place with the number k m +1, counting only the free places remaining 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 in (n-1) way, and so on. Thus, we get all possible permutations of n mismatched elements.
We illustrate this for 5 subjects (120 permutations) and permutations No.
77 77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!
Not being a practical programmer, I will nevertheless make assumptions (theoretical)) how such decomposition could be used. You can divide the total number of possible permutations into subbands 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. Factorial decomposition 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.