Shuffling two related sets together

Question

Given two sets of values $a_1, a_2, ... a_n$ and $b_1, b_2, ... b_n $ what would be a good way to shuffle them together while keeping $a_i$ and $b_i$ at least $gap$ spots apart?

For example, if we have A B C and a b c, then b A C a B c is a valid 2-gap shuffle, but not a valid 3-gap shuffle (because of the a's placement).

The obvious solution is to shuffle each set the same way and then append one to another. A slight variation is then also swap some element pairs ($a_j$ and $b_j$). These are no bueno however, because I am after an actually random shuffle across the entire combined set.

They way I have it now is - combine two sets, shuffle them, then traverse from the front and check for the constraint violation. If an item is in violation, i.e. we saw its twin less than gap spots back, then swap it with the first element from the tail that resolves the violation. This clearly doesn't guarantee to converge for every shuffle, so when it doesn't, reshuffle the whole thing and restart. Very crude, but works well for gap values that are substantially smaller than the set size.

Is there a better, non-restarting way to do the same?

Answer 1

If you need something that is guaranteed to be unbiased -- i.e., that will generate each possible valid outcome with equal probability -- I don't know of a way to achieve this efficiently. The simplest way to achieve it is with brute force: Generate a full solution, e.g., with the Fisher-Yates shuffle, then test whether it satisfies the constraints, and start over if it doesn't. You can gain a small speed advantage by restarting Fisher-Yates as soon as you detect a constraint violation (this is allowed since no later decision made by the algorithm can undo an existing violation).

If you aren't bothered by some potential bias, the following simple method takes $O(n^2)$ time:

1. Randomly shuffle the $a_i$.
2. For $i$ from 1 to $n$:
   • Pick a random location in the valid ranges for $b_i$ (there could be two, one on each side of $a_i$'s location) and insert it there.

This works because inserting a new value never causes an existing feasible solution to become infeasible, because all pair distances stay the same or increase by 1. Note that this approach likely introduces bias, since values inserted early in step 2 will on average be pushed further apart than values inserted late. Inserting the $b_i$ in random order might help.

You could improve the time complexity to $O(n\log n)$ by replacing the array with a self-balancing binary search tree, but my feeling is that that's probably overkill for a practical application. If the running time of the naïve algorithm is too high, it's probably easier just to shrink the constant in front of the $n^2$ by leaving regular "gaps" in the original array.

NOTE: This algorithm can still fail if the gap is $> \lfloor n/2 \rfloor$: If $a_1$ ends up in the middle, there will be no valid locations for $b_1$ in the first iteration of step 2. In this case you can either rerun it, or (likely at the cost of further bias) pick some other $i$ value to work with on that loop iteration. To see that there always exists an $i$ value that will work whenever the gap is $< n$:

1. Initially, there are two known-working $i$ values, corresponding to whichever $a_i$s landed in the first and last positions.
2. After the first $b_i$ is inserted, the second and second-to-last positions hold valid $i$ values.
3. In general, after $k$ insertions of $b_i$ values, there are $2(k+1)$ known-working $i$ values, at most $k$ of which have been used already.