Minimum number of dice rolls to get a random permutation

Question

Suppose that there are $n$ objects, for simplicity labeled 1 to $n$. You have an unbiased $k$ sided dice.

What is the minimum number of times you need to roll the dice to get an algorithm that samples a uniformly random permutation of $[n] = \{1,2,\dots, n\}$?

For example, if you had a unbiased coin (i.e. 2 sided dice), then to get a random permutation of $[n]$, it is enough to flip the coin $n-1$ times (by arranging 1 to $n$ as the leaves of tree and then flipping coins to see who "wins" among two child nodes. The total number of coin flips here will be $1+2+4+..+\frac{n}{2} = n-1$)

For a $k$ sided dice, my intuition is that using one dice roll you can totally order $x$ numbers such that $x! \leq k$ and $(x+1)! > k$.

So the minimum number of $k$ sided dice rolls needed would be $\sum_{i=0}^{ log_x(n)-1} x^i = \frac{n-1}{x-1}$ using a similar tree structure.

This makes sense to me for when $k$ is a "perfect" factorial (i.e. a factorial of a natural number) since there are no extra numbers on the dice that could come up and when $n$ is a perfect power of $k$. But what about when this doesn't hold?

Edit: Actually, the algorithm above doesn't work but I would still like to know the answer to the original question

Answer 1

The answer is to express $n$ in base-$k$. Then you can express $n$ with $\log_k(n)$ base-$k$ numerals and just roll a $k$-sided die for each numeral.

Obviously, $\log_k(n)$ might not be an integer. In that case, you just round up. Thus the number of dice to roll $d$ is given by: $$ d = \lceil \log_k(n) \rceil. $$

Then do like so: roll $d$ dice. If the base-$k$ number implied by the rolls is greater than $n$, reject it and reroll all $d$ dice. (That is important; otherwise your sample will not be uniformly drawn.)

After this is done, relabel the remaining numbers in $\{1,\ldots,n\}$, decrement the set size to $n-1$, and redo the above. Your best case is you make $\sum_{i=2}^n\lceil\log_k(i)\rceil$ die rolls.

Answer 2

Unless all the prime factors of $n$ are also factors of $k$ there is no finite answer. With $m$ rolls of the die you have $k^m$ possible results. You can divide them as evenly as possible into $n$ classes, but there will be a remainder. You then have to roll again. If there is more than one possible remainder, you can keep the information of what it is. For example, let $n=11, k=7$. One roll doesn't have enough possibilities to tell anything, so you need at least two. Two rolls gives you $7^2=49$ equiprobable results. You can assign $44$ of them to the $11$ objects and in those cases you have a selection. In $5$ of the $49$ cases you don't, so you roll again. You now have $35$ results, and you can assign $33$ of those to objects. There are $2$ left over and you roll again. We can't guarantee success in any given number of rolls, but the probability of failure gets very small quickly.

The reason you can guarantee success if the prime factors of $n$ are also factors of $k$ is that there is some $k^m$ that is divisible by $n$ and the remainder will be $0$.