文章/答案/技术大牛

发布

社区首页 >问答首页 >在限制元素移位范围的同时洗牌列表

问在限制元素移位范围的同时洗牌列表
EN

Stack Overflow用户

提问于 2013-01-26 06:53:55

回答 3查看 321关注 0票数 2

随机洗牌数组可以很容易地求解。我想做一个洗牌，但有一个附加的限制，任何元素的移动都被限制在一个范围内。因此，如果最大允许移位= 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]

arrays

algorithm

range

shuffle

回答 3

Stack Overflow用户

发布于 2013-01-26 13:45:41

这是可能的，这是一个确切的覆盖问题，并可能(我没有测试它，但我会证明这一说法)有效地解决了一个ZDD。

精确覆盖问题对于每个元素都有布尔决策变量，所以如果n = 0，有元素就会有很多变量，对于n = 1，除了端点，每个元素都有三个变量，每个元素都有两个变量，等等。

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

编辑:实际上，我现在不太确定这一点，特别是与瓷砖的可比性，这似乎越来越令人怀疑，但我仍然怀疑ZDD将是可管理的大小。

在合理大小的ZDD上，可以有效地生成无偏差(即每个解都有相同概率)的随机解(它对应于在“不超过n个位置”-rule下有效的置换)。

这可能不是最好的方法，但它表明，不使用暴力是有可能做到的。

票数 2

Stack Overflow用户

发布于 2013-01-26 13:30:40

输入InputArray：表示整数的数组
输入NumberCount：InputArray中的整数数
输入ShuffleRange：允许数字跳转的有效范围
ShuffleWindowSize：进行交换的处理窗口。它的值是ShuffleRange +1
ShuffleIndexArray：洗牌窗口中输入数字的索引，无效索引将是INT_MIN

初始化ShuffleIndexArray

对于(idx =0；idx < ShuffleWindowSize；idx++) { ShuffleIndexArrayidx = 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数组来跟踪索引。

票数 1

Stack Overflow用户

发布于 2013-01-26 19:06:11

听起来，对于每一个可能的输出都有相同的概率，你不会太挑剔。一种简单的解决方案可能是执行等价于冒泡排序的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在最终列表中最早出现的位置是ii-n：只有当元素接收到代理值ii-n/2.，并且以元素ii-n开头的每个元素至少收到ii-n/2.的代理值时，才会发生这种情况。相同的上界参数。

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

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/14534654

复制

相似问题

问在限制元素移位范围的同时洗牌列表
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在限制元素移位范围的同时洗牌列表EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在限制元素移位范围的同时洗牌列表
EN