<p>See <a href="https://doi.org/10.1145/3009909" rel="nofollow noreferrer">https://doi.org/10.1145/3009909</a> for a careful analysis of the number of random bits required to generate a random permutation.  (It's open-access, but it's not easy reading! Bottom line: if carefully implemented, all of the usual methods for generating random permutations are efficient in their use of random bits.)</p>

<p>And... if your goal is to generate a random permutation rapidly for large N, I'd suggest you try the MergeShuffle algorithm.  An <a href="https://arxiv.org/abs/1508.03167" rel="nofollow noreferrer">article published in 2015</a> claimed a factor-of-two speedup over Fisher-Yates in both parallel and sequential implementations, and a significant speedup in sequential computations over the other standard algorithm they tested (Rao-Sandelius).  </p>

<p>An implementation of MergeShuffle (and of the usual Fisher-Yates and Rao-Sandelius algorithms) is available at <a href="https://github.com/axel-bacher/mergeshuffle" rel="nofollow noreferrer">https://github.com/axel-bacher/mergeshuffle</a>.  But caveat emptor!  The authors are theoreticians, not software engineers.   They have published their experimental code to <a href="https://github.com/axel-bacher/mergeshuffle" rel="nofollow noreferrer">github</a> but aren't maintaining it.  Someday, I imagine someone (perhaps you!) will add MergeShuffle to GSL.  At present <code>gsl_ran_shuffle()</code> is an implementation of Fisher-Yates, see <a href="https://www.gnu.org/software/gsl/doc/html/randist.html?highlight=gsl_ran_shuffle" rel="nofollow noreferrer">https://www.gnu.org/software/gsl/doc/html/randist.html?highlight=gsl_ran_shuffle</a>.</p>

<p><a href="https://i.stack.imgur.com/7Idp6.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7Idp6.jpg" alt="Runtimes of Fisher-Yates, Rao-Sandelius, and MergeShuffle algorithms, in parallel and serial implementations"></a></p>

<p><a href="https://i.stack.imgur.com/cB4se.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cB4se.jpg" alt="Average number of random bits used by our implementation of various random permutation algorithms over 100 trials."></a></p>
random permutation
<p>I would like to genrate a random permutation as fast as possible.
The problem: The knuth shuffle which is O(n) involves generating n random numbers.
Since generating random numbers is quite expensive.
I would like to find an O(n) function involving a fixed O(1) amount of random numbers.</p>

<p>I realize that this question has been asked before, but I did not see any relevant answers.</p>

<p>Just to stress a point: I am not looking for anything less than O(n), just an algorithm involving less generation of random numbers.</p>

<p>Thanks</p>