How to find the number of permutations of a number?

Question

Algorithms

How to find the number of unique permutations of a number, excluding combinations where 0 is in front? The number can contain up to 10 digits. Example:
1200: [1200,1002,1020,2001,2010,2100,120,102,210,201,100,200,10,20,12,21,1,2] = 18
112: [112,121,211,12,21,11,1,2] = 8
102: [102,120,201,210,12,21,10,20,1,2] = 10
What literature should I read?

Answer 1

This is combinatorics.
If there were no restriction that the first character is not 0, then it would be much simpler. A common technique in combinatorics is to count the number of all possible options, and then subtract the number of "bad" options. Temporarily allow zero to be the first digit, solve the problem. Then we fix zero in the first position and count how many such options and subtract them. To do this, you can cross out one zero from the number, solve the same problem.
Also, your formula is about to add an empty number ("") to the answer. Let's solve it and subtract 1 at the end.
Also, obviously, the result depends only on the number of each digit in the original number, but not on their order.
So let f(a0,a1,...a9) be how many ways there are to arrange some of a0 zeros, a1 ones, a2 twos, and so on. (zero may be at the beginning, the number may be empty).
Answer to the problem f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). The last term counts options starting from zero. It is not subtracted if there are no zeros in the number. -1 in the middle subtracts an empty number from the answer (but it is not in the last term, because we also attribute 0 at the beginning and the empty number must be counted).
Now the most interesting part, the formula for f(a0,a1,...a9). I did not find a closed formula, but I figured out how to count with an algorithm.
You can divide all variants by the number of characters in the number (n), from 0 to the sum a0...a9. Let's think about where nines can be? i <= a9 of them will be included in the answer. They can be in C(n, i) positions. It remains to place the rest of the digits in ni positions.
The following dynamic programming emerges:
F(i, n) - how many ways to place the first i digits in n positions (maybe not taking all the digits).
F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, nj)*C(n, j)
F(0, n>0) = 0
F(i,0) = 1.
The answer is sum(k=0..a0+...+a9) F(9, k)
The function has an implicit parameter array a[] of the numbers of all digits, but I don’t I include dynamics in the parameters, because it does not need to be memoized.
Don't forget that in order to calculate the second dynamics, for f(a0-1,...a9) you will need to completely clean up the memeization, because the a array has changed.
This algorithm runs in O(9*n), where n is the length of the input number.
Here is an example for the input number 112: all digits that are not in the number can be thrown out of consideration and work with the array a={2,1} (it's too much to write for all ten digits).
F(0,0) = 1
F(0,1) = 0
F(0,2) = 0
F(0,3) = 0
F(1, 0) = 1
F(1,1) = F(0 , 1)*C(1,0) + F(0,0)*C(1,1) = 1
F(1,2) = F(0,2)*C(2, 0)+ F(0 ,1)*C(2,1) + F(0,0)*C(2,2) = 1
F(1,3) = F(0,3)*C(3, 0)+ F(0 ,2)*C(3,1) + F(0,1)*C(3,2) = 0
F(2,0) = 1
F(2,1) = F(1,1)*C( 1, 0) + F(1,0)*C(1,1) = 2
F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
F(2,3) = F(1,3)* C(3, 0) + F(1.2)*C(3.1) = 3
Answer F(2.3)+F(2.2)+F(2.1)+F(2.0) = 3+3+2+1= 9.
Subtract 1 (an empty number) and get 8 numbers, as in your example for 112.