1
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Aug 29 '12 at 17:27
  • $\begingroup$ Please don't cross post. Nobody suggested you should. Someone suggested a migration, and even that was dubious. $\endgroup$ – CodesInChaos Aug 29 '12 at 18:12
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Sorry, But I don't want to use any buffer to store anything. $\endgroup$ – Rahul Aug 29 '12 at 17:31
  • 3
    $\begingroup$ @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? $\endgroup$ – poncho Aug 29 '12 at 17:32
  • $\begingroup$ I believe he wants successive calls to the generator to produce the demonstrated outputs. $\endgroup$ – Stephen Touset Jan 10 '15 at 23:23
  • $\begingroup$ The required memory of the algorithm is the same as the data of the output. If you can't handle that in memory, how can you handle it in the output... this just doesn't make any sense. $\endgroup$ – tylo Jan 13 '15 at 15:08
  • $\begingroup$ @tylo: actually, it does make sense. One of the possible ways of doing the output is provide a function that, given $i$, gives you the $i$th member of the permutation. However, Rahul has never said how we wants the output represented, so we're just guessing... $\endgroup$ – poncho Jan 13 '15 at 15:17
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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)? $\endgroup$ – maaartinus Aug 31 '12 at 0:23
  • $\begingroup$ @maaartinus: I tend to think so, but it would deserve some careful analysis. $\endgroup$ – Thomas Pornin Aug 31 '12 at 13:12
0
$\begingroup$

If the permutation will fit in memory then the previous answer is the best approach. If it won't work then you might consider a linear congruential generator (LCG) of the form y = A * x + C. There is a lot of theory there (Knuth is always a good place to start for this). If you want N elements then you need to design a and b relative to N to get the full permutation. Different N and types of N have different rules. If you want multiple permutations then change A and / or C randomly based on the necessary rules for N will give you a large choice of permutations. If you want all possible permutations then you really need to store the permutation and use a shuffle algorithm. In the case where the LCG approach will work, you don't care about the quality of the generated random sequence since you want the entire sequence. You only care that the maximal period can be obtained.

|improve this answer
$\endgroup$
  • $\begingroup$ LCG's are nonrandom, in the sense that they're easy to distinguish from a random permutation given just a few elements. Depending on what the permutation will be used for, Thomas's suggestion would be better (assuming that you can't hold the entire buffer in memory) $\endgroup$ – poncho Jan 10 '15 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.