1
$\begingroup$

Is there a function

permute(size, seed, i) -> j

that runs in constant time that computes a pseudorandom permutation? In other words,

[permute(size, seed, 0), permute(size, seed, 1), ..., permute(size, seed, size - 1)]

should be a pseudorandom shuffle of the numbers

[0, 1, ..., size - 1]

A linear congruential generator is close to workable (I don't need strong randomness guarantees for my application), but I want an algorithm that works for any size, and there needs to be a way to incorporate the seed.

Improve this question
$\endgroup$
2
  • $\begingroup$ Given a function permute2(size2, seed, i) that only works for power-of-two size2 values, you can choose the smallest size2 >= size and repeatedly call permute2 until it returns something < size. This runs in expected constant time. Will flesh this out into a full answer if no-one else bites. $\endgroup$ Commented Mar 27 at 3:10
  • $\begingroup$ ...and power-of-two permutations are easy to do, such as using a Feistel network. $\endgroup$ Commented Mar 27 at 4:36

1 Answer 1

Reset to default
1
$\begingroup$

Use format-preserving encryption. If you search for "format-preserving" on this site and on Crypto.SE, you'll find many references. See, e.g., Incremental generation of random permutations?, Pseudo random, unqiue integer numbers in a given range, etc.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.