Random access random permutations

Question

I want to generate a very large pseudorandom permutation p : [0,n-1] -> [0,n-1], and then compute m specific values p[i], where m << n. Is it possible to do this in O(m) time? The motivation is a large parallel computation where each processor only needs to see a small piece of the permutation, but the permutation must be consistent between processors.

Note that in order to help in the parallel case, different processes computing disjoint sets of i values shouldn't accidentally produce p[i] == p[j] for i != j.

Mostly a duplicate of http://stackoverflow.com/questions/10054732/create-a-random-permutation-of-1-n-in-constant-space. — Geoffrey Irving, Dec 29 '12 at 01:59

Jed · Answer 1 · 2012-12-29T02:32:29.180

EDIT: There is a much more clever algorithm based on block ciphers that I think Geoff will write up.

There are two common algorithms for generating permutations. Knuth's shuffle is inherently sequential so not a nice choice for parallelism. The other is random selection with retry any time repetition is encountered. Random selection is clearly equivalent when applied in any order, thus I propose the following simple algorithm:

Randomly sample candidate p[i] in [0,n-1] for each i in Needed (in parallel).
Remove all non-collided entries from Needed, as well as (optionally) some deterministic choice from the collisions (e.g., keep p[i] if i < {j | p[j] = p[i]}).
Repeat from step 1 with new (smaller) set Needed.

Since we haven't lost entropy in this process, the result is essentially equivalent to sequential random sampling in some different order, starting with the locations i that did not collide (we just didn't know that order in advance). Note that if we used the computed value in a comparison, for example, we would have introduced bias.

This solution does answer the question as stated, but doesn't solve the motivating problem where different parallel processes need to coordinate which permutation is chosen. I'll edit the question. — Geoffrey Irving, Dec 29 '12 at 02:17

score 0 · Answer 2 · answered Dec 29 '12 at 01:50

0

An example very low strength version:

Generate 2k = O(1) random integers a_i,b_i in [0,n-1], with a_i relatively prime to n.
Pick a weak permutation wp : [0,n-1] -> [0,n-1], say w(i) = i with all the but the high bit flipped.
p[i] = b_0 + a_0 * wp(b_1 + a_1 * wp(... i ...))

answered Dec 29 '12 at 01:50

Geoffrey Irving

6,483
4
32
40

What is k referring to? – mako Oct 13 '13 at 06:00
$k$ is a small integer. However, this answer should be ignored: here is the real one: http://scicomp.stackexchange.com/questions/4923/random-access-random-permutations – Geoffrey Irving Oct 13 '13 at 20:32

Random access random permutations

2 Answers2

Linked