arrays - 在限制元素移位范围的同时打乱列表

Question

随机shuffling一个数组很容易解决。我想洗牌，但增加了一个限制，即任何元素的移动都被限制在一个范围内。因此，如果允许的最大移位 = n，则由于混洗，任何元素都不能在任一方向上移动超过 n 步。

给定这个数组，n=3:

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

这将是一个有效的洗牌:

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

虽然这些是无效的:

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

(注意范围不是旋转的)

我们正在寻找一种简单有效的方法来实现这一目标。最好就地进行，但如果可以提供良好的解决方案，则可以使用第二个数组。

一个简单的入门解决方案是，使用第二个数组:

for element in array1:
  get legal index range
  filter out indexes already filled
  select random index i from filtered range
  array20[i] = element

编辑:

这是关于@ruakh 提出的概率失真问题，如果算法首先以相等的概率处理终端元素:

乍一看，我认为概率方差会随着数组大小的增加而减小，但事实似乎并非如此。下面的一些快速测试(我仓促编造了这个，所以可能有错误)。由于概率失真很大，我认为这是 Not Acceptable 作为一般情况，但对于我自己的应用程序，我可以像我在评论中所说的那样接受它。

import itertools

n = 2

def test(arlen):
    ar = range(arlen)
    lst = list(itertools.permutations(ar))
    flst = [l for l in lst if not illegal(l)]

    print 'array length', arlen
    print 'total perms: ', len(lst)
    print 'legal perms: ', len(flst)

    frst = [0] * (n+1)
    for l in flst:
        frst[l[0]] +=1

    print 'distribution of first element: ',frst

def illegal(l):
    for i in range(len(l)):
        if abs(l[i]-i)>n: return True

if __name__=="__main__":
    arlen = range(4,10)
    for ln in arlen:
        test(ln)

------------ n=2
array length 4
total perms:  24
legal perms:  14
distribution of first element:  [6, 4, 4]
array length 5
total perms:  120
legal perms:  31
distribution of first element:  [14, 10, 7]
array length 6
total perms:  720
legal perms:  73
distribution of first element:  [31, 24, 18]
array length 7
total perms:  5040
legal perms:  172
distribution of first element:  [73, 55, 44]
array length 8
total perms:  40320
legal perms:  400
distribution of first element:  [172, 128, 100]
array length 9
total perms:  362880
legal perms:  932
distribution of first element:  [400, 300, 232]

------------ n=4
array length 4
total perms:  24
legal perms:  24
distribution of first element:  [6, 6, 6, 6, 0]
array length 5
total perms:  120
legal perms:  120
distribution of first element:  [24, 24, 24, 24, 24]
array length 6
total perms:  720
legal perms:  504
distribution of first element:  [120, 96, 96, 96, 96]
array length 7
total perms:  5040
legal perms:  1902
distribution of first element:  [504, 408, 330, 330, 330]
array length 8
total perms:  40320
legal perms:  6902
distribution of first element:  [1902, 1572, 1296, 1066, 1066]
array length 9
total perms:  362880
legal perms:  25231
distribution of first element:  [6902, 5836, 4916, 4126, 3451]

Answer 1

有可能将其视为一个精确覆盖问题，并且可能(我没有测试它，但我会证明这一说法是正确的)用 ZDD 有效地解决。

对于每个元素可以放入结果的每种方式，精确覆盖问题都会有 bool 决策变量，因此如果 n = 0，变量的数量将与元素的数量一样多，因为n = 1 每个元素都有三个变量，除了末端，每个元素有两个变量，等等。

如果 n 明显小于数组的大小，这意味着“相距甚远”的决策变量不会直接影响彼此。这应该使 ZDD 的大小保持合理，因为它在结构上与例如小瓷砖的瓷砖问题相当。

编辑:实际上我现在不太确定这一点，尤其是与平铺的可比性似乎越来越令人怀疑，但我仍然怀疑 ZDD 的大小是可控的。

在合理大小的 ZDD 上，可以有效地生成无偏差(即每个解决方案具有相等概率)随机解决方案(对应于在“不要移动超过 n 个地方”规则下有效的排列).

这可能不是最好的方法，但它表明无需蛮力也可以做到这一点。