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?