# Can you help me with this Random Number Generator function?

By someone's suggestion, I am posting this question from math.stackexchange.com.

I want to find out a suitable function or algorithm, which can provide a random sequence like this…

Input: $3$
Output: $\{1,2,3\}$ or $\{1,3,2\}$ or $\{2,1,3\}$ or $\{2,3,1\}$ or $\{3,1,3\}$ or $\{3,2,1\}$

Same as if I will enter a number $N$, output will be a random permutation of the set $\{1,2,...N\}$.
How can a I write this type of algorithm? And can you help me understand the logic behind it?

-
No closed form function can describe a truly random permutation by definition. But if $N = 2^k$, then block ciphers come a significant fraction of the way. –  Thomas Aug 29 '12 at 17:27
Please don't cross post. Nobody suggested you should. Someone suggested a migration, and even that was dubious. –  CodesInChaos Aug 29 '12 at 18:12

The classical way to generate a random permutation is the Fisher-Yates shuffle; it takes an underlying random number generator, and produces a random permutation. With just a bit of care, it can generate each permutation with equal probability (assuming the underlying random number generator outputs are independent and uniformly distributed).

The only downside is that the algorithm requires N to be small enough so that you hold the entire permutation in memory; that doesn't sound like that's a problem from you.

-
Sorry, But I don't want to use any buffer to store anything. –  Rahul Taneja Aug 29 '12 at 17:31
@RahulTaneja: you said you wanted the output to be the random permutation. If you didn't want to use a buffer, how is the function or algorithm supposed to return you the permutation? –  poncho Aug 29 '12 at 17:32

If for some reason the solution given by @poncho does not please you (e.g. you want $N$ to be on the magnitude of a few billions but you do not have a few gigabytes of RAM), then there are other solutions, in which you get the permutation as an evaluable procedure (in other words, a block cipher).

A practical solution is the Thorp shuffle. It is approximate, but the approximation can be made as good as needed by adding more rounds (except that, as a Feistel-derivative, it implements only even permutations, so if the attacker knows the output for $N-2$ inputs he can compute the last two outputs with 100% certainty). There is also a "perfect" solution but it involves some floating-point operations which needs potentially unbounded accuracy, so in practice it is very expensive.

-
Can't any even-permutations-only generating cipher be made "perfect" by a trivial postprocessing conditionally switching two outputs (with a 50% probability based on the key)? –  maaartinus Aug 31 '12 at 0:23
@maaartinus: I tend to think so, but it would deserve some careful analysis. –  Thomas Pornin Aug 31 '12 at 13:12