arrays - 具有距离限制的数组洗牌算法

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

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