0
$\begingroup$

I have determined that if you have N numbers from 0 to N-1 then there are exactly N! (factorial) unique combinations. If this is the case then the unique combinations should be deterministic/formulaic.

For example let's say on a small scale N = 4 that means the unique number of combinations is N! or 4! = 4 * 3 * 2 (excluding the 1 because it's not necessary). If we write this out we can prove it:

     0       1       2       3
0    0123    1023    2013    3012
1    0132    1032    2031    3021
2    0213    1203    2103    3102
3    0231    1230    2130    3120
4    0312    1302    2301    3201
5    0321    1320    2310    3210

You can also say that the total number of unique combinations for each starting number 0, 1, 2 & 3 is equal to (N-1)!. So if we look at the first line of unique combinations starting with 0 we can see that there are 6 combinations or 3! = 3 * 2 = 6.

What I can't figure out is how to wrap this up into a formula. For example let K represent the unique combination's position, e.g. K = 13 which would give us 2031 (starting from 0 and counting top-to-bottom and then left-to-right).

So what I am trying to figure out is that given the arguments N (length of combinations), K (the iteration of the combination) and I (index of the number in the combination) how can I get each number of a combination at a given index?

combination(N,K,I)
combination(4,13,2)
    24 combinations...
    K = 13 or 2031...
    3 at index 2 (starting from 0)...

BONUS: I noticed that ALL unique combinations from 0 to N-1 where the number of unique combinations is N! that if you take any two combinations and subtract them from eachother you get a |number| that is ALWAYS divisible by 9--unless N = 1 which is 1.

For example if N = 2, then 2! = 2, which gives us 01 and 10. (10 - 01) = (9 modulo 9) = 0. Or if 4! and we take (3210 - 1302) = (1908 modulo 9) = 0. If you go up to 11! = 39,916,800 you can take (012345678109 - 012345678910) = (|-801| modulo 9) = 0.

$\endgroup$
1
$\begingroup$

What you want is the Factorial number system.

Let's work through your example: $N=4$, $K=13$.

It might be less confusing to explain if we look at combinations of the letters $(A,B,C,D)$ instead. So we have a list of 24 words, starting with $ABCD$ at the $K=0$ position of the list, and $DCBA$ at the $K=23$ position in the list.

As you already noted, there are $N!=24$ combinations of $(A,B,C,D)$ on the list, and there are $(N-1)!=6$ that start with $A$, followed by another 6 that start with $B$, etc.

The one we are looking for, at $K=13$, falls within the third block of 6, because $K = 2\cdot 6+1$. This means that the first letter of our combination is $C$, the third from the list of symbols $(A,B,C,D)$.

The remainder $K' = K-2\cdot6 = 1$ tells us which one of this sub-list of 6 combinations to choose. This sub-list consists of the combinations of the remaining letters $(A,B,D)$. This is exactly the same problem, but with $N'=3$. This list splits into 3 blocks of size $2!$, of which the first block starts with $A$, the second block starts with $B$, the third block starts with $D$.

This time $K' = 0\cdot2+1$, so the combination we are looking for lies in the first block, those which have $A$ as the next Letter. So our combination starts with $CA$, and $K'' = K'-0\cdot2 = 1$ indicates which combination we need to choose from the sub-sub-list of 2.

and so on.

So now to put it together more succinctly into a straightforward procedure:

  1. Represent the number $K$ into the factorial number system, using $N$ 'digits'.
    In the example we have $K = 2\cdot3!+0\cdot2!+1\cdot1!+0\cdot0!$, so it is $2010_!$ in factorial representation.

  2. Use the digits in the factorial to select the items from $(A,B,C,D)$.
    In the example, we pick $2,0,1,0$:
    $(A,B,C,D)$, pick $2$, i.e. $C$.
    $(A,B,D)$, pick $0$, i.e. $A$.
    $(B,D)$, pick $1$, i.e. $D$.
    $(B)$, pick $0$, i.e. $B$.
    This gives $CADB$ as the combination at $K=13$.


As for your bonus, Have a look at the Digital Root. You are subtracting two numbers with the same digital root, which means you are subtracting two numbers with the same residue modulo 9, resulting in a number that is 0 modulo 9, i.e. divisible by 9.

$\endgroup$
  • $\begingroup$ Is there any way to do it without having to break the list down from ABCD to ABD to BD to D? Just get 2010 in another form which would push out the correct order in a constant list of 1234? $\endgroup$ – FatalSleep Feb 25 '18 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.