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.

Given a positive integer:

$$\begin{align*} N \in \mathbb{Z}^+ \end{align*}$$

I would like a function:

$$\begin{align*} f : \mathbb{Z}^2 \rightarrow \mathbb{Z} \end{align*}$$

such that

$$\begin{align*} (f(N,0), f(N,1), f(N,2), \dots , f(N,N-1)) \end{align*}$$

is a deterministic but "pseudo-random" permutation of the identity N-vector:

$$\begin{align*} (0, 1, 2, \dots, N-1) \end{align*}$$

What is a simple closed form or algorithm for $f$?

share|improve this question
    
Does this help: en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle? –  Aryabhata Feb 15 '12 at 23:39
    
N is very large, I would prefer a solution in O(1) space and O(1) time if possible. –  Andrew Tomazos Feb 16 '12 at 0:22
    
a) How can it be in $O(1)$ time if you want to produce $N$ output values? b) What is the rest of the function $f$ doing there? If you're only interested in the values where the first argument is $N$, why don't you define a function of one variable? –  joriki Feb 21 '12 at 20:01
    
joriki: I think the idea is that this single function is supposed to work for all values of $N$. So one might have $\ldots, f(3,0) = 2, f(3,1) = 0, f(3,2) = 1, f(4,0) = 1, f(4,1) = 2, f(4,2) = 0, f(4,3) = 3, \ldots$ for example. –  Michael Lugo Feb 21 '12 at 22:15
    
I mean O(1) time/space per call to f, so yes O(N)/O(1) time/space for the whole permutation. –  Andrew Tomazos Feb 22 '12 at 0:28
add comment

1 Answer

up vote 0 down vote accepted

Let $\alpha=(\sqrt5-1)/2$, let $g(n)$ be the integer nearest $\alpha n$ among the integers relatively prime to $n$, and let $f(r,s)$ be $(s+g(r))g(r)$ reduced modulo $r$.

share|improve this answer
    
Is it so that for any x relatively prime to n and for any k, that (k,x+k,2x+k,3x+k,...,(n-1)+k) mod (n,n,...,n) is a permutation of (0,1,2,...,n-1) ? –  Andrew Tomazos Feb 22 '12 at 0:44
    
Yes, provided that your $n-1$ was a typo for $(n-1)x$. –  Gerry Myerson Feb 22 '12 at 2:03
    
Yes, typo. What is the significance of (sqrt(5) - 1)/2 here? Why is your choice of x and k superior to any other? –  Andrew Tomazos Feb 22 '12 at 4:07
    
I didn't say it was superior to any other. But $\alpha$ holds the record for being hardest real irrational to approximate by rationals, and staying away from rationals means staying away from sequences that look like they are periodic with a short period. The $+g(r)$ was an effort to introduce some randomness into the values of $f(r,0)$, and maybe there are better offsets that could be used. Why not experiment a little bit and see? –  Gerry Myerson Feb 22 '12 at 5:02
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.