Method for deterministic shuffling

66 Views Asked by At

Is there a way to map an integer (uniquely) from a range [0,N) to a (possibly) different number in the range [0,N)? Another way to say this is that I'd like a deterministic map that shuffles any number in the range [0,N). In my case, N is always a power of 2. I'm not looking for a way to shuffle a vector/range. I want to "shuffle" an isolated element in a deterministic and unique way.

As a concrete example, I'm looking for a way to implement shuffle_id below.

size_t idx          = generate_idx(N);      // Arbitrary function, generates idx in [0,N)
size_t idx_shuffled = shuffle_idx(idx, N);  // Shuffles/redistributes idx in [0,N)

I've tried looking at hash functions (see an example below), but for some settings (and maybe in general), there will be collisions.

size_t shuffle_idx(size_t idx, size_t N){
  size_t hash_v = (PRIME1 * idx) % PRIME2; // Where PRIME2 > N
  return hash_v % N;
}

If there are any suggestions about this or pointers to resources on this problem or a related one, I'd appreciate it.

EDIT

To address @Progman's comments below about the requirements for my shuffle function.

I'd like the shuffle_idx function to transform the value by something more complicated than just cyclicly rotating using a constant shift and a modulo.

An extremely inefficient way to accomplish what I'm looking for looks like this:

size_t bad_shuffle_idx(size_t idx, size_t N){
  std::vector<size_t> map_idx(N);
  std::iota(map_idx.begin(), map_idx.end(), 0);
  std::mt19937 g(0); // Seed with 0 so it's deterministic
  std::shuffle(map_idx.begin(), map_idx.end(), g);  
  
  return map_idx[idx];
}
0

There are 0 best solutions below