Javascript，数组随机播放但保持一定距离

Question

我需要一个函数来随机排列元素数组，但元素之间的最小距离为 2。

让我解释一下我的情况，我有一个不间断的输入，每 200 毫秒不断向我发送单词。我还有一个包含预定义单词的独特数组。

我收到的每个单词，我都会检查它是否可以，如果在我的条件下可以，我想把它放在我的数组中。但是，在那一刻，我不再需要一个唯一的数组，所以我的数组中可能会有 double ，事实上，我想要 double 符合我条件的单词。

好的，所以，问题来了，我收到的每个 OK 词，我想把它放在数组中然后打乱它，它可以是 double 的，但是，在这种情况下，我想在这之间保持距离单词和数组中的其他相同单词。

例子:
唯一数组:[foo, bar, baz, qux]
我启动程序，它每 200 毫秒向我发送一次单词。
得到:fubar > OK
插入:[foo, bar, baz, qux, fubar]
得到:橙色 > OK
插入:[foo, bar, baz, qux, fubar, orange]
得到:青柠 > OK
插入:[foo, bar, baz, qux, fubar, orange, lime]
得到:qux > OK (DOUBLE)

正确插入:[foo, bar, baz, qux, fubar, orange, lime, qux]
正确插入:[foo, qux, bar, baz, qux, fubar, orange, lime]
插入错误的方式:[foo, bar, baz, qux, qux, fubar, orange, lime]

第一个距离为 3，第二个距离为 2 ...第三个错误，距离为 0。

任何人都可以给我一个好的方法和/或逻辑来做到这一点？对于类似的情况，最小距离 = 2。

提前谢谢你。

---

编辑 1:用户 jfriend00 显示了数组充满 double 的可能性，假设它们都具有最小距离，并且下一个要插入的元素没有正确的位置适合，那么，我不能插入它。

---

编辑 2:我还认为我必须避免插入可能无法进行下一次插入的位置，如下所示:

得到:苹果> OK
(A) 以正确的方式插入:[baz, qux, fubar, orange, lime, apple]

得到:qux > OK(双)
(A) 正确插入:[baz, qux, fubar, orange, qux, lime, apple]
(B) 插入错误的方式:[baz, qux, fubar, orange, lime, qux, apple]

在这里，插入被距离 3 (B) 处插入的 qux“chop ”。

得到:qux > OK(双)
(A) 正确插入:[baz, qux, fubar, orange, qux, lime, apple, qux]
(B) 插入错误的方式:[baz, qux, fubar, orange, lime, qux, apple]

Answer 1

这是一种一次添加一个项目的算法。基本思想是这样的:

1. 获取要添加到列表中的项目
2. 如果列表为空，直接添加
3. 如果列表不为空，则生成一个包含所有可能位置的数组，将其添加到列表中
4. 随机选择其中一个可能的位置
5. 通过检查当前位于该位置的项目和之前的项目来检查该位置是否合法。如果合法，请将其添加到您刚刚选中的两项之间。
6. 如果该位置不合法，则从所有可能位置数组中删除该位置并随机选择另一个位置。将其从数组中删除可确保您不会再次尝试相同的非法位置
7. 重复，直到您找到一个合法的位置(所以您将它插入那里)或直到您用完所有可能的位置(没有地方放它，因为您已经检查了所有可能的位置)

工作演示:http://jsfiddle.net/jfriend00/5xGV3/

var sourceOfItems = ["apple", "grapefruit", "orange", "lime", "pear", "peach", "apricot"];

function insertNextItem(list, item) {

    // special case an empty items array
    if (list.length === 0) {
        list.push(item);
        return true; 
    }

    // build an array of possible insertion positions
    // items.length + 1 means to add it at the end
    var possiblePositions = [];
    for (var i = 0; i < list.length + 1; i++) {
        possiblePositions.push(i);
    }

    // select random position, see if that is allowed
    // if not, remove it from the possibilities and select a new random position
    while (possiblePositions.length > 0) {
        var randIndex = Math.floor(Math.random() * possiblePositions.length);
        var pos = possiblePositions[randIndex];
        // check if this position is allowed
        if (list[pos] !== item && (pos === 0 || list[pos - 1] !== item)) {
            // position is allowed, insert it and return
            list.splice(pos, 0, item);
            return true;
        } else {
            // was not allowed, so remove this possiblePositions choice
            // and let the loop try again
            possiblePositions.splice(randIndex, 1);
        }
    }
    return false;    
}

function buildList(sourceItems, num) {
    var items = [];
    for (var i = 0; i < num; i++) {
        insertNextItem(items, sourceOfItems[Math.floor(Math.random() * sourceOfItems.length)]);
    }
    return items;
}

function go() {
    var list = buildList(sourceOfItems, 20);
}

有关可以处理任何最小距离的更通用版本，请参阅此处的 jsFiddle:http://jsfiddle.net/jfriend00/LxWNa/

附言查看 jsFiddle 时，查看调试控制台输出非常有趣，因为它会向您显示尝试了哪些位置无效以及哪些项目无法插入数组，因为没有合法位置。