# pseudo-random permutation of $[0,N)$

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$?

-
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
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$.
Yes, provided that your $n-1$ was a typo for $(n-1)x$. –  Gerry Myerson Feb 22 '12 at 2:03
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