How to generate a permutation uniformly by repeating using an one-bit uniform random generator? 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?
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"), 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" :-).



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 have devised a nice general framework based on a popular random generation framework introduced by Wilf and Nijenhuis and formalized by Flajolet et al.. 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.