Good Day
I know about how Factorial Number System is useful to find permutations and also find the the index of a permutation.
For example, permutation $[1, 3, 4, 0, 2]$ has index ($0$ – based) $1 \cdot 4! + 2 \cdot 3! + 2 \cdot 2! + 0 \cdot 1! + 0 \cdot 1! = 40$ where the constant is the index ($0$ – based) of the number in the unused numbers.
However, what if the arrangement contains repetitions. Consider $[0, 0, 1, 1, 2, 2]$. Now arrangement $[2, 2, 1, 1, 0, 0]$ should have index $\frac{6!}{2! \cdot 2! \cdot 2!} – 1 = 89$, but if I go the usual way and consider the index in only the distinct unused numbers, I get $2 \cdot 5! + 2 \cdot 4! + \cdots$ which is already larger than $89$. Even doing $2 \cdot \frac{120}{2 \cdot 2} + 2 \cdot \frac{24}{2 \cdot 2} + 1 \cdot \frac{6}{2} + 1 \cdot \frac{2}{2}$ gives $76$.
Thus, is there a simple way to extend this system for repetitions, so that given an array of possibly non-distinct numbers, I can find the lexicographic index of the arrangement and from the (lexicographic) index, find the arrangement without casework?
Thanks
Best Answer
The index of a binary string can be found using the combinatorial number system.
For example, $N=100=1100100_2$ can be considered as an element of the k-combination set $\binom{7}{3}$.
As such it can be written $\{6,5,2\}$, where each element is a set bit in $N$. We then have $100=2^6+2^5+2^2$.
Its (zero-based) index is then given by the formula:
$$\binom{6}{3}+\binom{5}{2}+\binom{2}{1}=20+10+2=32$$
(There are $\binom{7}{3}=35$ in total.)
It works by examining each bit separately. For example, the formula states that there are exactly $\binom{6}{3}$ 3-combinations before the $6$, because $0111000 _2< 1000000_2$. Similarly there are $\binom{5}{2}$ 2-combinations before $0100000$, and so on. Therefore every $N$ has a unique representation.
For a permutation with repetition, a similar process can be used.
For example, consider $[3,2,2,0,3,1,3]$. We first break this into its components for each digit:
We follow a similar process as with the binary string for each component, and multiply by a positioning factor which is determined by its associated multinomial.
For example, the $3$ row becomes $\binom{6}{3}+\binom{2}{2}+\binom{0}{1}=20+1+0=21$.
The total number of permutations is $\frac{7!}{3!2!1!1!}=840$. The size of the 3-block is $\binom{7}{3}=35$, and so $\frac{840}{35}=24$ gives the multiplying factor.
The $2$ row is $\binom{3}{2}+\binom{2}{1}=5$ because it is nested into the 3-block. The multiplying factor is $\frac{24}{\binom{4}{2}}=4$.
After working out the last two rows, the index is:
$$21\cdot24+5\cdot4+0\cdot2+0\cdot1=524$$.