2

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.

Discipol
  • 131
  • 2
    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

1 Answers1

0

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.

Ross Millikan
  • 374,822