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
    Does this help: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle?2012-02-15
  • 0
    N is very large, I would prefer a solution in O(1) space and O(1) time if possible.2012-02-16
  • 0
    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?2012-02-21
  • 0
    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.2012-02-21
  • 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
    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) ?2012-02-22
  • 0
    Yes, provided that your $n-1$ was a typo for $(n-1)x$.2012-02-22
  • 0
    Yes, typo. What is the significance of (sqrt(5) - 1)/2 here? Why is your choice of x and k superior to any other?2012-02-22
  • 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