1
$\begingroup$

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

  • 0
    I mean$O(1)$time/space per call to f, so yes O(N)/O(1) time/space for the whole permutation.2012-02-22

1 Answers 1

0

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

  • 0
    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?2012-02-22