# How can make a function accepts X from 0, 1 … N and returns Y from shuffle( 0, 1 … N )?

I am searching for a function which has input a number X from 0, 1, 2, 3....N. Its result should be Y which belongs to a permuted version of the input's set.

The results must be unique and thus all of them are generated. Now, I am aware / don't mind that for all lists of 0, 1, .... N, the same results will be outputed. This is expected and fine, I just want the results to be the input shuffled around.

For example: N = 10. I call the function 10 times with: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and it might return 7, 1, 5, 2, 9, 8, 3, 0, 4, 6.

I found this function :

function perm( x )
{
return x * 833 % N;
}


Where 833 can be any large-ish prime number. This makes good-ish results but they are always with a repeating pattern. See for N = 16: 0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13

Imagine it looks like 3 shark fins. Basically my question is, how do I make a function that does what I have described but with a more chaotic shuffle?

I CANNOT pregenerate a permutation of 0, 1...N.

-
Your restriction on pregenerating a permutation seems very arbitrary. If you want a deterministic answer, the function you want is essentially just that - a complicated way of describing a pregenerated permutation. If you're allowed a source of randomness, you should just look up any old shuffling algorithm. If you want a deterministic version, you could do the same thing but provide the algorithm with a predetermined seed. – user73445 Apr 30 '13 at 19:54
Until you can give a rigorous definition of what conditions make it an acceptable shuffle, it is not really a mathematical problem. – Thomas Andrews Apr 30 '13 at 20:09
@Thomas I am unsure what variable degrees of shuffle are. Lets put it this way: if you put the values into a chart, you wouldn't see a visual pattern, like can immediately see in my formula. user73445 X is the nr of already generated values. It represents the number of entries in my database. There is nowhere to put the pregenerated characters, thus when I add another entry in my database, I get the nr of existing entries, generate using the F(x) I seek, and add the entry with the result. – Discipol Apr 30 '13 at 20:28
But again "visible pattern" is not a mathematical definition. You can't solve a problem without a definition. Even in pure randomness, humans see patterns. – Thomas Andrews Apr 30 '13 at 20:31
Bad case: 1, 20, 6, 26, 5, 34..... This is what I meant. – Discipol Apr 30 '13 at 21:02

One approach is to pick some big number $n$, say of order $N!/2$. Use that to find the $n^{\text{th}}$ lexicographic permutation of $N$. The first number is $\lfloor \frac n{(N-1)!} \rfloor$. Then form $n'=n-\lfloor \frac n{(N-1)!} \rfloor$ The second number is the $\lfloor \frac {n'}{(N-2)!} \rfloor$th one of what is left (so increment by $1$ if higher than the first). Keep going, reducing the factorial in the denominator by $1$ each time.
{"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": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7723960280418396, "perplexity": 245.64742105782432}, "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": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-18/segments/1461860126502.50/warc/CC-MAIN-20160428161526-00102-ip-10-239-7-51.ec2.internal.warc.gz"}