Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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