arrays - 带距离限制的数组shuffle算法

Question

例如，我有以下数组:

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

我想打乱这个数组。但有一个距离限制:每个元素的新位置必须从 old_position - n 到 old_position + n。

例如，如果n = 4，那么这个数组对我有好处:

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

我试图想出一些算法。但我没有成功。

Answer 1

这里有一些可能有帮助的伪代码。请注意，该算法的重点是遵守距离规则，从而牺牲了过程中的均匀性*。

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

_{* 在我看来，问题定义需要非均匀分布，因为例如，数组开头和结尾的值比数组中间的值具有更少的合法位置。因此，尝试开发一种可证明统一的算法似乎是一件愚蠢的事情。}