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

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?

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$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?

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 $\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
Link
Anton Menshov
  • 8.1k
  • 5
  • 34
  • 90
Tweeted twitter.com/#!/StackSciComp/status/286062891365462017
deleted 10 characters in body
Source Link

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?

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)$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?

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$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?

Source Link
Loading