Shuffle An Array So That No Element Moves More Than K Places

Question

I have an array, and I'd like to shuffle the array so that no element moves more than K places from its initial position in the array. So for example, if K is 2, and the original array is:

[1,2,3,4,5,6,7,8]

this is a valid permutation:

[1,3,2,5,4,8,6,7]

but this is not:

[1,2,5,4,6,8,3,7]

because the 3 has moved 4 places.

Is there a way to do this so that it's a perfectly random shuffle (in other words, all permutations that satisfy this criteria are equally likely?)

The word ``shufle`` is very generic here. You could just interchange two variable with distance less than ``K``. Is that considered a shuffle ? — Schidu Luca, Jan 17 '18 at 18:42
@SchiduLuca: note the parenthetical comment: pair interchanges don't satisfy that criterion. Not that *I* have a solution yet ... :-) — Prune, Jan 17 '18 at 19:03
Yes, exactly as @Prune has mentioned, I don't know how pairwise exchanges can be performed so that every permutation is equally likely. — Curious Student, Jan 17 '18 at 19:05
Also, note that filtering (generate all permutations, then remove the ones violating the distance requirement) is a trivial, but obviously *bad* solution (time-consuming at **O(n!)**) for array size N >> K. We would strive for something that works in the neighborhood of each element, such as **O(NK)**, or **O(N K!)** at worst. — Prune, Jan 17 '18 at 19:09
Possible duplicate of [Controlling distance of shuffling](https://stackoverflow.com/questions/30747690/controlling-distance-of-shuffling) — גלעד ברקן, Jan 18 '18 at 00:48

astraujums · Answer 1 · 2018-01-17T20:58:50.343

Below is a Python code to do this but the proof that all permutations are equally likely is left as an exercise for the reader (meaning, I don't know how to prove it and I am not sure the probabilities are really equal :) ).

The idea is this:

For each position in the resulting array we choose an element from the original array that is not further than the desired distance and that has not been chosen before.
If at some position we find out that we have an not-chosen element from the original array exactly the maximum distance behind the current position, we choose that element (the last-chance choice).

import random

initial_array = [x for x in range(1, 10)]
max_distance = 3
element_taken = [(i < max_distance) or i > (len(initial_array) + max_distance - 1) for i in range(len(initial_array) + max_distance * 2)]

result = [0] * len(initial_array)

for i in range(len(initial_array)):
    print ("Position", i)
    print ("Original", initial_array)
    print ("  Result", result)
    print ("   Taken", element_taken)
    if not element_taken[i]:
        element_taken[i] = True
        result[i] = initial_array[i - max_distance]
        print ("Had to use last-chance move from %d to %d" % (i - max_distance, i))
        continue
    possible_positions = [position for position in range(i - max_distance, i + max_distance + 1) if not element_taken[max_distance + position]]
    print ("Possible positions", possible_positions)
    position = random.choice(possible_positions)
    print ("Moving %d to %d" % (position, i))
    result[i] = initial_array[position]
    element_taken[max_distance + position] = True

print ()
print ("   Final", result)

OK, I checked - it does NOT have the same probability for each possible outcome. For most positions (save both ends of the array), the most likely position where the value comes from is from maximum allowed distance to the left (the "last-chance" option). A possible "quick-fix" solution could be applying some offset-dependent weights when choosing the source position. — astraujums, Jan 17 '18 at 22:37

Shuffle An Array So That No Element Moves More Than K Places

1 Answers1