Don't use p for the permutation, since we use p for something else in the lone answer.

I have a large number of parallel processes and a large integer $$n$$, and want to randomly partition the integers $$[0,n)$$ among the processes with only $$O(1)$$ communication.

One nice way to do this would to generate a pseudorandom permutation $$p \in S_n$$$$\pi \in S_n$$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?

edited tags
Anton Menshov
• 8.1k
• 5
• 34
• 90
I have a large number of parallel processes and a large integer $$n$$, and want to randomly partition the integers $$[0,n)$$ among the processes with only $$O(1)$$ communication.
One nice way to do this would to generate a pseudorandom permutation $$p : [0,n) \to [0,n)$$$$p \in S_n$$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?