JavaScript中随机选择数组元素且不重复

Question

所以，我正在尝试从一个数组中选择一个随机条目，然后使得该特定条目不会再次被选择，直到选择了每个条目为止。 基本上，我不想看到任何相同的条目，直到选择了数组中的所有条目。 所以，如果这是我的数组...

keywords =
[
 "ppc",
 "games",
 "advertise",
 "meta",
 "home",
 "gaming",
 "welcome"
]
var keyword = keywords[Math.floor(Math.random()*keywords.length)]
document.write(keyword);

我不希望看到以下输出：

我不想看到这样的输出：

meta, advertise, home, meta, gaming, welcome, ppc, welcome

由于在所有选项都被选择之前，meta 被第二次选择了。我希望看到更像这样的内容：

meta, advertise, gaming,ppc, welcome, home, games, advertise, ppc,

由于之前并没有多次选择任何条目，因此每个条目都是随机选择的。（如果你没有注意到差异，第二个循环从第二个“advertise”开始）。

但是，正如你可以从我上面发布的代码中看到的那样，我不知道该怎么做。我曾经看到过一些例子，被随机选择的条目实际上已经从数组中删除了，但这不是我想要做的。我只想每个条目都被选中一次，然后重新启动该过程。

有人知道这个代码吗？

- Andreas Jarbol

---

可能是随机数数组的重复问题。 - Matt Ball

Answer 1

您可以使用 Array.sort() 函数来随机排序。

// random sort function
function shuffle(a, b)
{
   return Math.random() > 0.5 ? -1 : 1;
}

var keywords = ["ppc", "games", "advertise", "meta", "home", "gaming", "welcome"];

var randomKeywords = keywords.sort(shuffle); // new instance of a sorted randomly copy of the array

alert(randomKeywords);

更新：

对于洗牌，更好的解决方案是使用Fisher-Yates Shuffle算法，可以在这个答案中找到。

function shuffle(array)
{
  var m = array.length, t, i;
  while (m > 0) 
  {
 i = Math.floor(Math.random() * m--);
 t = array[m];
 array[m] = array[i];
 array[i] = t;
  }
  return array;
}

var keywords = ["ppc", "games", "advertise", "meta", "home", "gaming", "welcome"];

shuffle(keywords); // shuffles the array

alert(keywords);

- Mark Knol

---

这在我的Linux上的Firefox和Opera上不起作用。我需要从shuffle()中去掉-1。如果如何处理排序函数中的0是实现相关的，那么在shuffle()的主体中使用return (Math.random() > 0.5) ? -1 : 1;怎么样？ - sparklewhiskers

Answer 2

一个非常简单的方法是在每次选择一个随机元素时使用 splice，一旦数组为空，就用原始值重新填充它。

示例：

(function () {
    var arr = [];

    window.getRandomThing = function () {
        if (arr.length === 0) {
            refill();
        }

        return arr.splice(Math.random() * arr.length, 1)[0];
    };

    function refill () {
        arr = [1,2,3,4,5];
    }
} ());

- HoLyVieR

Answer 3

您可以复制原始数组，然后使用.splice()在随机索引处获取一个值，并从副本数组中删除它。

由于每次都会减少一次副本的长度，因此您可以简单地使用while(copy.length)。 示例：http://jsfiddle.net/fMXTF/

var keywords = [
 "ppc",
 "games",
 "advertise",
 "meta",
 "home",
 "gaming",
 "welcome"
];

var copy = keywords.slice();

while( copy.length ) {

    var keyword = copy.splice( Math.floor(Math.random()*copy.length), 1 );
    document.write(keyword + '<br>');

}

请注意，随机数是基于copy.length计算的，由于使用了.splice()方法，在每次迭代中都会减少1。因此，它确保随机数始终基于复制品的当前length。

- user113716

Answer 4

如果您不介意数组的变化，您可以随机排列数组中的元素顺序，然后从第一个元素到最后一个元素打印数组。

或者

您可以创建另一个值为1到N（其中N是元素数量）的数组。随机排列该数组的顺序，然后将其用作索引，当您从第一个元素到最后一个元素迭代时使用它。

- Hogan

Answer 5

从 user113716 借鉴了一下，但稍作优化。

var arr = [
    "ppc",
    "games",
    "advertise",
    "meta",
    "home",
    "gaming",
    "welcome"];

Array.prototype.shuffle = Array.prototype.shuffle || function () {
    var copy = this.slice(), arr = [];
    while (copy.length) arr.push(copy.splice((Math.random() * copy.length) << 0));
    return arr;
};

alert(arr.shuffle());

- yckart

Answer 6

在哈希表中存储你所见过的数字（索引），当你尝试查看一个新单词时，可以检查哈希表，如果已经看到该单词，则生成一个新数字。但是，请确保检查哈希表长度是否与数组长度相同。

这样可以避免改变数组。

- HaloZero

---

但是假设你有一个包含1000个索引的数组，每次迭代找到唯一索引的概率会呈指数级增长。对于最后一次选择，你只有1000分之一的机会结束函数。因此，循环将额外迭代1000次，甚至更多。当你添加索引时，这也变得更加棘手。你的选择函数可能需要几分钟才能结束。 - Krythic

最佳解决方案是选择一个随机索引，然后将该索引与您选择的索引交换到数组的末尾，然后再次使用(array.Length - 1 - i)循环。您保证了O/n的最佳选择。 - Krythic