Looking for a limited shuffle algorithm

Question

I have a shuffling problem. There is lots of pages and discussions about shuffling a array of values completely, like a stack of cards.

What I need is a shuffle that will uniformly displace the array elements at most N places away from its starting position.

That is If N is 2 then element I will be shuffled at most to a position from I-2 to I+2 (within the bounds of the array).

This has proven to be tricky with some simple solutions resulting in a directional bias to the element movement, or by a non-uniform amount.

Answer 1

You're right, this is tricky! First, we need to establish some more rules, to ensure we don't create artificially non-random results:

• Elements can be left in the position they started in. This is a necessary part of any fair shuffle, and also ensures our shuffle will work for N=0.
• When N is larger than an element's distance from the start or end of the array, it's allowed to be moved to the other side. We could tweak the algorithm to forbid this, but it would violate the "uniformly" requirement - elements near either end would be more likely to stay put than elements near the middle.

Now we can actually solve the problem.

1. Generate an array of random value in the range i + [-N, N] where i is the current index in the array. Normalize values outside the array bounds (e.g. -1 should become length-1 and length should become 0).
2. Look for pairs of duplicate values (collisions) in the array, and recompute them. You have a few options:
   • Recompute both values until they don't collide with each other, they could both still collide with other values.
   • Recompute just one until it doesn't collide with the other, the first value could still collide, but the second should now be unique, which might mean fewer calls to the RNG.
   • Identify the set of available indices for each collision (e.g. in [3, 1, 1, 0] index 2 is available), pick a random value from that set, and set one of the array values to selected result. This avoids needing to loop until the collision is resolved, but is more complex to code and risks running into a case where the set is empty.
3. However you address individual collisions, repeat the process until every value in the array is unique.
4. Now move each element in the original array to the index specified in the array we generated.

I'm not sure how to best implement #2, I'd suggest you benchmark it. If you don't want to take the time to benchmark, I'd go with the first option. The others are optimizations that might be faster, but might actually end up being slower.

This solution has an unbounded runtime in theory, but should terminate reasonably quickly in practice. Again, benchmark and test it before using it anywhere critical.