1
$\begingroup$

Given a number N between 2 and 9, consider the integers that can be formed using each digit in the set {1, 2, . . . , N} exactly once. For instance, if N is 3, the integers we can form are 123, 231, 312, 132, 321 and 213. If we arrange these in increasing order, we get the list {123, 132, 213, 231, 312, 321}. The fourth number in this list is 231. In general, given two numbers N and K, the task is to compute the number at position K when all integers formed using the digits {1, 2, . . . , N} exactly once are arranged in ascending order. For instance, the example worked out above corresponds to N = 3 and K = 4.

Find the the answer for the following values of N and K. N = 5, K = 76

How am I meant to do this?

$\endgroup$
  • $\begingroup$ I think this has to do with the binary representation of K... $\endgroup$ – Nicolas FRANCOIS Nov 12 '17 at 8:11
  • $\begingroup$ How though? I can write a program to compute this, but how do I do this on pen and paper? $\endgroup$ – Ben Ritmico Nov 12 '17 at 8:36
1
$\begingroup$

You can find an algorithm of linear time like this.

Note that if you order the numbers of $N$ digits in an increasing order, then the first $(N-1)!$ numbers will have $1$ as first digit, the next $(N-1)!$ numbers will have $2$ as a first digit and so on. So determing in which subset of $(N-1)!$ numbers $K$ is determines the first digit. So to determine the first digit find the number:

$$M_1 = \left[\frac{K-1}{(N-1)!} \right]$$

and choose $(M_1+1)$-th number in the set $\{1,2,...,N\}$. Then delete the chosen number from the list and repeat recursively this algorithm while you write all the digits. But this time you have to subtract $M_1 \cdot (N-1)!$ from $K$ and perform the same algorithm with using the new number as $K$.


In particular let's take a look at the case $N=5$, $K=76$.

We have $M_1 = \left[\frac{76-1}{(5-1)!}\right] = 3$ and then the $4$-th number in $\{1,2,3,4,5\}$ is $4$. Pick it as first digit and then the set of digits is $\{1,2,3,5\}$.

Now perform again. Assing $76 - 3\cdot 24 = 4$ to $K$ and we have: $M_2 = \left[\frac{4-1}{(4-1)!}\right] = 0$. So pick $1$ as a second digit.

Again. Assign $4 - 0\cdot 6 = 4$ to $K$ and then $M_3 = \left[\frac{4-1}{(3-1)!}\right] = 1$, so pick $3$ as the third digit, as the set of digits is $\{2,3,5\}$ and we need the second smallest.

Repeating this two more times will give you that the $76$-th number in the sorted sequence is $41352$

$\endgroup$
  • $\begingroup$ Why do we need to keep re evaluating k for each digit? $\endgroup$ – Ben Ritmico Nov 12 '17 at 15:49
  • $\begingroup$ @BenRitmico As I've said first you find in which subset of $(N-1)!$ numbers the $K-$th number will be. After we determine we're working in that subset now. As we need to determine the rest $(N-1)$ digits we need to the find in which subset of $(N-2)!$ the number is, but we consider the first number starting with our chosen digit to be in the first position. We don't care about the rest of the possible combinations. Our new "universe" is the number with starting digit as ours. $\endgroup$ – Stefan4024 Nov 12 '17 at 17:45
  • $\begingroup$ Yeah, sorry for my initial comment, the representation you need to consider is different than the binary one (but still, an interesting math exercise :-) $\endgroup$ – Nicolas FRANCOIS Nov 13 '17 at 18:46

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.