2

随机打乱数组很容易解决。我想做一个洗牌，但有一个额外的限制，即任何元素的变化都被限制在一个范围内。因此，如果 max allowed shift ，则由于洗牌，任何元素都不能在任一方向上= 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 提出的概率失真问题，如果算法首先以相等的概率处理终端元素：

乍一看，我认为概率方差会随着数组大小的增加而减小，但情况似乎并非如此。下面的一些快速测试（我匆忙炮制了这个，所以可能有错误）。由于概率的失真很大，我认为它不能作为一般情况接受，但对于我自己的应用程序，我可以忍受它，就像我在评论中所说的那样。

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]
4

3 回答 3

2

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

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

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

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

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

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

于 2013-01-26T13:45:41.953 回答
1

听起来您对每个可能的输出具有相等的概率并不太挑剔。一个简单的解决方案可能是等效于n冒泡排序，但不是对元素进行排序，而是随机选择是否在每一步交换两个元素。这种方法也可以让您就地进行随机化。您可以执行以下操作：

import random
def shuffle_list(list, n):
    for ipass in xrange(n):
        for ielt in xrange(len(list) - 1):
            if random.randrange(2):
                temp = list[ielt]
                list[ielt] = list[ielt + 1]
                list[ielt + 1] = temp

编辑：对不起，我应该多考虑一下。我描述的方法不起作用——在第一遍中，第一个元素冒泡到列表末尾的概率非零。不知怎的，我错过了。

我想我现在真的没有答案，但至少有一个想法：为原始列表中的每个元素分配一个等于 的代理值，原始列表中元素的索引在ii + random.uniform(-n/2., n/2.)哪里；ii然后根据这个代理值对原始列表进行排序。然后，最早ii可以出现在最终列表中的元素是 position ii-n：只有当元素接收到代理值ii-n/2.并且以元素开头的每个元素都ii-n接收到至少 的代理值时，才会发生这种情况ii-n/2.。上限的参数相同。

在实践中，您可能希望使用稍宽的范围，可能类似于random.uniform(-n/2. - 0.49, n/2. + 0.5). 我还没有仔细计算过这个数学，但我认为这保持了距离约束。我也不完全确定可能列表的最终分布是什么。@Basel，我认为您对最初的建议是正确的，似乎更有可能让每个元素移动少量而不是大量移动。我认为这个解决方案应该更好，但我不能发誓。:-)

于 2013-01-26T19:06:11.953 回答
1
  • 输入InputArray：说整数数组
  • Input NumberCount: InputArray 中的整数个数

  • 输入ShuffleRange：一个数字允许跳转的有效范围

  • ShuffleWindowSize：发生交换的处理窗口。它的值为ShuffleRange +1

  • ShuffleIndexArray: Shuffle 窗口中输入数字的索引，无效索引将是INT_MIN

初始化ShuffleIndexArray

for (idx =0; idx < ShuffleWindowSize; idx++) {
  ShuffleIndexArray[idx] = idx;
}

过程InputArray

for (idx = 0; idx < NumberCount; idx++) {

    shuffleIdx = idx % ShuffleWindowSize;

    /* 1. Check if the Element has been moved from it's Original Position
     * 1.1 IF it was swapped already then move to next element
     * 1.2 ELSE perform shuffling within available window
     */
    if (idx != ShuffleIndexArray[shuffleIdx]) { /* was swapped already */
        goto LOOP_CONTINUE;
    }
    /* Get a random Index in the range [0, shuffleWinSize) */
    randomSwapIdx = rand() % shuffleWinSize; /* OffSet */

    /* Skip Invalid Indexes */
    if (INT_MIN == shuffleIndexArray[randomSwapIdx]) {
        for (jdx = randomSwapIdx + shuffleWinSize - 1; jdx > randomSwapIdx; jdx--) {
            if (INT_MIN != shuffleIndexArray[jdx % shuffleWinSize]) {
                randomSwapIdx = jdx % shuffleWinSize;
                break;
            }
        }
    }

    /* Get the actual index into InputArray */
    randomSwapIdx = ShuffleIndexArray[randomSwapIdx]; /*Actual Index*/

    /* Check if number gets to stay in original position */
    if (idx == randomSwapIdx) { /* Lucky Bugger */
        goto LOOP_CONTINUE;
    }

    /* Swapping of two numbers in InputArray */
    swapInt = inputArr[idx];
    inputArr[idx] = inputArr[randomSwapIdx];
    inputArr[randomSwapIdx] = swapInt;

    /* Update indexes in Shuffle-Window Array */
    ShuffleIndexArray[randomSwapIdx % ShuffleWindowSize] = idx;

    LOOP_CONTINUE:
    /* InputArray[idx] was processed.
     * Update ShuffleIndexArray */
    ShuffleIndexArray[shuffleIdx] =
            ((idx + ShuffleWindowSize) < NumberCount) ?
                    (idx + ShuffleWindowSize) : INT_MIN;
}

这是一个就地改组，除了我们需要另一个大小数组ShuffleWindowSize来跟踪索引。

于 2013-01-26T13:30:40.813 回答