# Random Sequence Generator function

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

I want to find out a function or algorithm, whichever is suitable, which can provide me a random sequence. Like

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. Actually I want to find out 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
– CodesInChaos Aug 29 '12 at 18:12

## 2 Answers

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.

-

1
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9231433272361755, "perplexity_flag": "middle"}