CODEWITHSUNDEEP
arraysalgorithmrandompermutationshuffle
Max
Max

Reputation: 1903

Algorithm of array shuffle with distance restriction

For example, I have the following array:

array numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

I want to shuffle this array. But there is one distance restriction: new position of each element must be from old_position - n to old_position + n.

For example, if n = 4, then this array is good for me:

array new_numbers = {2, 3, 4, 0, 1, 6, 5, 8, 9, 7}

I tried to think of some algorithm. But I did not succeed.

Upvotes: 2

Views: 240

Answers (1)

user3386109
user3386109

Reputation: 34829

Here's some pseudo code that may help. Note that the algorithm is focused on conforming to the distance rule, sacrificing uniformity* in the process. 

choose a random array index (call it "i" )
there's number at array[i] (call it "A")
set "count" to 0
for each "j" such that array[j] is a valid location for "A"
{
    there's a number at array[j] (call it "B")
    if ( "B" can be legally moved to array[i] )
        increment "count" 
}
generate a random number between 0 and count-1
find the index "j" that corresponds to that random number
swap array[i] with array[j]

repeat the above sequence a satisfactory number of times

* Seems to me that the problem definition requires a non-uniform distribution, since for example, the values at the start and end of the array have fewer legal positions than the values in the middle of the array. So trying to develop an algorithm that's provably uniform seems like a fool's errand.

Upvotes: 2

Related Questions