<p>Your solution does not work (or I don't understand it): the resulting permutation would not be uniformly random.</p>

<p>To Sasho Nikolov, this <em>is</em> a research topic and is actually the topic (among others) of a paper I have recently submitted, where I provide an optimal algorithm. I can give you an idea of the lower bound. Indeed, you would have to distinguish between n! different permutations, so theoretically you would need at least log2(n!) bits exactly. But Knuth and Yao show in their seminal paper (<a href="http://scholar.google.com/scholar?hl=en&amp;q=%22The%20complexity%20of%20nonuniform%20random%20number%22&amp;btnG=&amp;as_sdt=1,5&amp;as_sdtp=" rel="noreferrer">"The complexity of nonuniform random number"</a>), that because of "rounding errors" (to simplify), the actually random-bit complexity is between log2(n!) and log2(n!) + 2, that those are the best bounds, and in addition they provide an exact expression in terms of entropy of the distribution (in this case the uniform distribution).</p>

<p>It can (and has) been shown that the exact complexity involves fluctuations periodic in log2(n), much like the average complexity of divide-and-conquer algorithms such as QuickSort. (Such details are routinely hidden by the traditional sledge-hammer approach known as the "<a href="http://en.wikipedia.org/wiki/Master_theorem" rel="noreferrer">Master theorem</a>" :-).</p>

<p><img src="https://i.sstatic.net/GW3nl.png" alt="The (optimal) expected number of random bits (y-axis) needed to distinguish between N (x-axis) choices."></p>

<p>Now, supposing you have your random number X, the bijection between the number and the corresponding permutation is a subproblem of what is more largely referred to as "unranking". <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.9588&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Martinez and Molinero</a> have devised a nice general framework based on a popular random generation framework introduced by Wilf and Nijenhuis and formalized by <a href="http://algo.inria.fr/flajolet/Publications/gener.ps.gz" rel="noreferrer">Flajolet et al.</a>. But for permutations it is a much simpler problem: you consider the factorial-base expansion of X to get the random integers needed for the Fisher-Yates algorithm. See the following for more info:</p>

<p><a href="http://en.wikipedia.org/wiki/Factorial_number_system" rel="noreferrer">http://en.wikipedia.org/wiki/Factorial_number_system</a></p>

<p><a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="noreferrer">http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle</a></p>

<p><strong>EDIT:</strong> added the image which shows the optimal number of expected random bits needed to distinguish between N choices.</p>

CC BY-SA 3.0
2012-07-01T03:04:20.253Z
I'll remove my downvote of the question when and if the question is edited. The system has locked in my vote otherwise. Good explanation.
Josephine Moeller
CC BY-SA 3.0
2012-07-01T03:23:43.983Z
This is a nice answer. Maybe I misunderstood the question. I suspected that the *exact* randomness needed is a non-trivial question, but my impression was that the OP was asking about an algorithm optimal up to constants (and with the caveats of approximate uniformity due to rounding as you and Yuri pointed out), which is easier.
Sasho Nikolov
CC BY-SA 3.0
2012-07-01T03:48:16.157Z
@SashoNikolov: understandable :-) this is a topic that interests me so I chose to answer without using the Big-O notations which the asker used suggesting he might only be interested in an order. I added a plot to show the fluctuations.
Jérémie
CC BY-SA 3.0
2012-07-01T21:39:15.237Z
I thought your answer had some great insight that I hadn't really cared to think about before.
Josephine Moeller
CC BY-SA 4.0
2019-10-23T15:04:33.467Z
The paper referenced was [Optimal Discrete Uniform Generation from Coin Flips, and Applications](https://arxiv.org/pdf/1304.1916.pdf), I’m guessing?
jbapple
CC BY-SA 3.0
2012-07-01T02:52:08.207Z
2012-07-01T03:46:30.603Z
2012-07-01T03:46:30.603Z
Jérémie
<p>If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.</p>

<p>I have a solution:  run the one-bit random generator n*n times to decide if each pair of elements will be exchanged.</p>

<p>The complexity is O(n*n).</p>

<p>I want to know if there more efficiency solution? What is the lower bound for this problem?  </p>

CC BY-SA 3.0
2012-06-30T18:04:41.983Z
I think the lower bound is $O(n \log n)$ since you need to generate $\log n!$ random bits.
aelguindy
CC BY-SA 3.0
2012-06-30T18:31:25.987Z
BTW I don't think this is research-level, sounds like a homework exercise
Sasho Nikolov
CC BY-SA 3.0
2012-06-30T19:10:10.880Z
There is no algorithm that generates a random permutation uniformly using at most $N$ bits that *always* succeeds (for every $N$ and $n > 2$). An algorithm can either generate a random permutation only approximately uniformly (with an arbitrary precision) or generate a random permutation truly uniformly but fail with some small probability.
Yury
CC BY-SA 3.0
2012-06-30T20:36:28.360Z
It's also pretty easy to see that this is at most $O(n\log n)$ because you can generate a uniform random number in $[1..n]$ with $\lceil\log n \rceil$ calls to the 1-bit generator. Then you just use the usual algorithm.
Josephine Moeller
CC BY-SA 3.0
2012-06-30T20:38:44.380Z
Downvoted for scope.
Josephine Moeller
CC BY-SA 3.0
2012-06-30T22:47:04.927Z
@JohnMoeller: Only if $n$ is a power of $2$, and this is the heart of the original question.  You can't choose uniformly from $\{0,1,2\}$ with two coin flips.  You can, however, choose uniformly from $\{0,1,2\}$ with 3 _expected_ flips.
Jeffε
CC BY-SA 3.0
2012-06-30T22:48:08.260Z
@aelgundy: The statement "the lower bound is $O(n\log n)$" is formally meaningless.  ("Up to 50% off or more!")  You meant $\Omega(n\log n)$.
Jeffε
CC BY-SA 3.0
2012-06-30T22:50:53.717Z
@JɛﬀE Fair enough. I guess dropping the numbers between $n$ and $2^{\log n}$ is probably where I'm being sloppy.
Josephine Moeller
CC BY-SA 3.0
2012-07-01T02:58:37.653Z
@JɛﬀE: Agreed! The lower bound of expected flips to uniformly choose among {0, 1, 2} is 8/3.
Jérémie
CC BY-SA 3.0
2012-07-01T21:40:05.233Z
Un-downvoted after Jérémie's answer.
Josephine Moeller
<ds.algorithms><lower-bounds><randomized-algorithms>
How to generate a permutation uniformly by repeating using an one-bit uniform random generator?
konjac
# How to generate a permutation uniformly by repeating using an one-bit uniform random generator?

(Asked by: username_0 on 2012-06-30)

If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.

I have a solution: run the one-bit random generator n\*n times to decide if each pair of elements will be exchanged.

The complexity is O(n\*n).

I want to know if there more efficiency solution? What is the lower bound for this problem?

**Tags:** ds.algorithms, lower-bounds, randomized-algorithms
> **Comments:**
> **username_1**: I think the lower bound is $O(n \log n)$ since you need to generate $\log n!$ random bits.  
> **username_2**: BTW I don't think this is research-level, sounds like a homework exercise  
> **username_3**: There is no algorithm that generates a random permutation uniformly using at most $N$ bits that *always* succeeds (for every $N$ and $n > 2$). An algorithm can either generate a random permutation only approximately uniformly (with an arbitrary precision) or generate a random permutation truly uniformly but fail with some small probability.  
> **username_4**: It's also pretty easy to see that this is at most $O(n\log n)$ because you can generate a uniform random number in $[1..n]$ with $\lceil\log n \rceil$ calls to the 1-bit generator. Then you just use the usual algorithm.  
> **username_4**: Downvoted for scope.  
> **username_5**: @JohnMoeller: Only if $n$ is a power of $2$, and this is the heart of the original question.  You can't choose uniformly from $\{0,1,2\}$ with two coin flips.  You can, however, choose uniformly from $\{0,1,2\}$ with 3 _expected_ flips.  
> **username_5**: @aelgundy: The statement "the lower bound is $O(n\log n)$" is formally meaningless.  ("Up to 50% off or more!")  You meant $\Omega(n\log n)$.  
> **username_4**: @JɛﬀE Fair enough. I guess dropping the numbers between $n$ and $2^{\log n}$ is probably where I'm being sloppy.  
> **username_6**: @JɛﬀE: Agreed! The lower bound of expected flips to uniformly choose among {0, 1, 2} is 8/3.  
> **username_4**: Un-downvoted after Jérémie's answer.  

---

## 1 answers

### Answer by username_6 on 2012-07-01. Score: 22

Your solution does not work (or I don't understand it): the resulting permutation would not be uniformly random.

To Sasho Nikolov, this *is* a research topic and is actually the topic (among others) of a paper I have recently submitted, where I provide an optimal algorithm. I can give you an idea of the lower bound. Indeed, you would have to distinguish between n! different permutations, so theoretically you would need at least log2(n!) bits exactly. But Knuth and Yao show in their seminal paper (["The complexity of nonuniform random number"](http://scholar.google.com/scholar?hl=en&q=%22The%20complexity%20of%20nonuniform%20random%20number%22&btnG=&as_sdt=1,5&as_sdtp=)), that because of "rounding errors" (to simplify), the actually random-bit complexity is between log2(n!) and log2(n!) + 2, that those are the best bounds, and in addition they provide an exact expression in terms of entropy of the distribution (in this case the uniform distribution).

It can (and has) been shown that the exact complexity involves fluctuations periodic in log2(n), much like the average complexity of divide-and-conquer algorithms such as QuickSort. (Such details are routinely hidden by the traditional sledge-hammer approach known as the "[Master theorem](http://en.wikipedia.org/wiki/Master_theorem)" :-).

![The (optimal) expected number of random bits (y-axis) needed to distinguish between N (x-axis) choices.](https://i.sstatic.net/GW3nl.png)

Now, supposing you have your random number X, the bijection between the number and the corresponding permutation is a subproblem of what is more largely referred to as "unranking". [Martinez and Molinero](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.9588&rep=rep1&type=pdf) have devised a nice general framework based on a popular random generation framework introduced by Wilf and Nijenhuis and formalized by [Flajolet et al.](http://algo.inria.fr/flajolet/Publications/gener.ps.gz). But for permutations it is a much simpler problem: you consider the factorial-base expansion of X to get the random integers needed for the Fisher-Yates algorithm. See the following for more info:

<http://en.wikipedia.org/wiki/Factorial_number_system>

<http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle>

**EDIT:** added the image which shows the optimal number of expected random bits needed to distinguish between N choices.

> **Comments:**
> **username_4**: I'll remove my downvote of the question when and if the question is edited. The system has locked in my vote otherwise. Good explanation.  
> **username_2**: This is a nice answer. Maybe I misunderstood the question. I suspected that the *exact* randomness needed is a non-trivial question, but my impression was that the OP was asking about an algorithm optimal up to constants (and with the caveats of approximate uniformity due to rounding as you and Yuri pointed out), which is easier.  
> **username_6**: @SashoNikolov: understandable :-) this is a topic that interests me so I chose to answer without using the Big-O notations which the asker used suggesting he might only be interested in an order. I added a plot to show the fluctuations.  
> **username_4**: I thought your answer had some great insight that I hadn't really cared to think about before.  
> **username_7**: The paper referenced was [Optimal Discrete Uniform Generation from Coin Flips, and Applications](https://arxiv.org/pdf/1304.1916.pdf), I’m guessing?  

---

