如何高效地随机选择数组项而不重复？

Question

我知道这个问题以多种形式存在，但我未能找到一个关于效率的特定答案。

我有以下代码，它能正常运行。

我有一个包含10个项目的数组，从中随机选择一个项目(按enter键)。该代码保留最近5个选择的项目的数组，这些项目不能被随机选中(以避免长时间重复)。

如果chooseName()函数最初选择了在最近5次尝试中使用过的名称，它就会简单地停止并再次调用自身，重复此过程，直到找到“唯一”的名称为止。

我的两个问题：

1. 说这是一个"递归函数"是否正确？

2. 我担心在找到唯一名称之前，理论上这可能会循环很长时间 - 有没有更有效的方法来做到这一点？

谢谢您的任何帮助。

    var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
    var b = [];

    var chooseName = function () {
    var unique = true;
    b.length = 5;
    num = Math.floor(Math.random() * a.length);
    name = a[num];    
        for (i = 0; i < a.length; i++) {
        if (b[i] == name) {
            chooseName();
            unique = false;
            break;
            }
        }
        if (unique == true) {
        alert(name);
        b.unshift(name);
        }
    }


    window.addEventListener("keypress", function (e) {
        var keycode = e.keyCode;
        if (keycode == 13) {
        chooseName();
        }
    }, false);

- Russell

---

创建一个临时数组的副本，选中元素后从其中简单地删除它，当临时数组为空时再重新创建。这样做可以确保在数组耗尽之前不会出现重复的元素。 - Yuriy Galanter

当您从数组中选择一个项目时，删除它，以便无法再次选择它，并将其添加到所选项目的数组中。当该数组变得大于5时，将最旧的一个添加回原始数组中，以便可以再次选择它。 - Barmar

Answer 1

我喜欢评论者@YuriyGalanter的想法，即随机选择项目直到全部被选中，然后再重复选择，因此这里是一个实现：

function randomNoRepeats(array) {
  var copy = array.slice(0);
  return function() {
    if (copy.length < 1) { copy = array.slice(0); }
    var index = Math.floor(Math.random() * copy.length);
    var item = copy[index];
    copy.splice(index, 1);
    return item;
  };
}

var chooser = randomNoRepeats(['Foo', 'Bar', 'Gah']);
chooser(); // => "Bar"
chooser(); // => "Foo"
chooser(); // => "Gah"
chooser(); // => "Foo" -- only repeats once all items are exhausted.

- maerics

Answer 2

每当选择一个项目时，将其移动到数组的末尾，并从原始数组的array.slice(0, -5)中随机选择。

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];

var chooseName = function () {
    num = Math.floor(Math.random() * a.length - 5);
    name = a.splice(num,1);
    a.push(name);
}


window.addEventListener("keypress", function (e) {
    var keycode = e.keyCode;
    if (keycode == 13) {
        chooseName();
    }
}, false);

编辑：这也会产生一个副作用，即不会给列表末尾的任何变量带来不公平的劣势，因为它们不会在前N个调用中被考虑。如果这对你造成了问题，可以尝试在某个地方保留一个静态变量来跟踪要使用的切片大小，并将其最大化到B（在此例子中为5）。

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
B = 5; //max size of 'cache'
N = 0;

var chooseName = function () {
    num = Math.floor(Math.random() * a.length - N);
    N = Math.min(N + 1, B);
    name = a.splice(num,1);
    a.push(name);
}

- smakateer

Answer 3

我建议您使用underscore.js，这将非常简单。 shuffle函数的实现是均匀分布的，因此如果数组a包含更多数据，则重复的概率将很低。

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
b = _.shuffle(a).slice(0,5);
console.log(b);

- zs2020

---

谢谢。我目前试图避开使用库，因为我想学习纯JavaScript以确保我了解正在发生的事情。我将来会查看它。 - Russell

Answer 4

对于数组最简单的洗牌方法是：

['aaa', 'bbb', 'ccc'].sort(() => 0.5 - Math.random())

要访问，需先保存随机数组，然后：

1. 跟踪所在索引并访问该处的值，随意增加/减少索引，或
2. 在需要值时直接使用 .pop() 方法

- Stephen Saucier

---

我认为这并没有回答问题。这可能会导致选择相同的数组元素值（或前面的元素等）重复出现。 - isherwood

@isherwood 那并不是真的。请自行测试，不会有重复项。 - Stephen Saucier

这将对数组进行排序。你打算如何选择元素？也许在你的回答中提供更多细节会有所帮助。 - isherwood

@isherwood，已更新。 - Stephen Saucier

Answer 5

当您实例化Shuffler时，请将数组作为参数传递给它。它将创建数组的副本，并且每次调用next()时，它都会从副本中返回一个随机元素并将其从副本中删除，以确保不会重复。

var Shuffler = function(a) {
    var aCopy = [],
        n     = 0;

    // Clone array
    for (n=0; n<a.length; n++) {
        aCopy.push(a[n]);
    }

    this.next = function() {
        if (aCopy.length == 0) { return null; }

        var nRandom  = Math.floor(Math.random() * (aCopy.length + 1)),
            mElement = aCopy[nRandom];

        delete aCopy[nRandom];
        return mElement;
    }
}

var oShuffler   = new Shuffler([/* names go here */]),
    sRandomName = null;

while (sRandomName = oShuffler.next()) {
    console.log(sRandomName);
}

- Lex Podgorny

Answer 6

在我的特定情况下，我想随机更改一个框的颜色，但不要有任何连续重复的相同颜色。这是我想出的解决方案。使用while循环，我能够实现所需的结果。希望这能帮助某些人。

var colors = ["black","red","yellow","green","blueviolet","brown","coral","orchid","olivedrab","purple"];

function getRandomColor(){
    num = Math.floor(Math.random() * 10); // get a random number between 0-9
    return colors[num];
}

function randomizeColor(){
    currentColor = document.getElementById("box").style.backgroundColor; // got the current color of the box on the page.
    randomColor = getRandomColor(); 
    while (randomColor == currentColor){ // if we get the same color as the current color, try again.
        randomColor = getRandomColor();
    }
    document.getElementById("box").style.backgroundColor = randomColor; // change box to new color
}

<!DOCTYPE html>
<html>
<head>
    <title>Random Color Box</title>
</head>
<body>

    <p>Press the buttons to change the box!</p>
    <div id="box" style="height:150px; width:150px; background-color:red; margin:25px; opacity:1.0;"></div>

    <button id="button" onclick="randomizeColor()">Random Color</button>

    <script type="text/javascript" src="javascript.js"></script>

</body>
</html>

- sd6363

Answer 7

洗牌的标准方法被称为费雪-耶茨算法。只要随机数生成器是公平的，这种方法就是公平的。

它的工作原理是从未经洗牌的数组的副本中随机删除项目，直到没有任何项目剩余。

let arr = [1,2,3,4,5,6,7]

let shuffled = arr.reduce(([a,b])=>
  (b.push(...a.splice(Math.random()*a.length|0, 1)), [a,b]),[[...arr],[]])[1]

console.log(shuffled)

- Andrew Parks

---

返回的文本：为了可读性，使用以下代码可以洗牌数组：var shuffledArray = myArray.reduce( ([original, shuffled]) => { shuffled.push(...original.splice(Math.random() * original.length | 0, 1)) return [original, shuffled] }, [[...myArray], []] )[1] - toddmo

Answer 8

这对我来说非常完美，没有任何重复。

   var Random_Value = Pick_Random_Value(Array);

---

function Pick_Random_Value(IN_Array) 
{
    if(IN_Array != undefined && IN_Array.length > 0)
    {
        var Copy_IN_Array = JSON.parse(JSON.stringify(IN_Array));
        if((typeof window.Last_Pick_Random_Index !== 'undefined') && (window.Last_Pick_Random_Index !== false))
        {
            if(Copy_IN_Array[Last_Pick_Random_Index] != undefined)
            {
                Copy_IN_Array.splice(Last_Pick_Random_Index,1);
            }
        }

        var Return_Value = false;

        if(Copy_IN_Array.length > 0)
        {
            var Random_Key = Math.floor(Math.random() * Copy_IN_Array.length);
            Return_Value = Copy_IN_Array[Random_Key];
        }
        else
        {
            Return_Value = IN_Array[Last_Pick_Random_Index];
        }

        window.Last_Pick_Random_Index = IN_Array.indexOf(Return_Value);
        if(window.Last_Pick_Random_Index === -1)
        {
            for (var i = 0; i < IN_Array.length; i++) 
            {
                if (JSON.stringify(IN_Array[i]) === JSON.stringify(Return_Value)) 
                {
                    window.Last_Pick_Random_Index = i;
                    break;
                }
            }
        }


        return Return_Value;
    }
    else
    {
        return false;
    }
}

- Mohamad Hamouday

Answer 9

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", 
"Elizabeth", "Ted", "Caroline","Brezza","Elephant","Jack","Virat"];    
let b=[a[Math.floor(Math.random() * a.length)]];

for(let i=1; i<=12; i++){
  let t = a[Math.floor(Math.random() * a.length)];
  const n = b.indexOf(t);
   if (n >= 0) {
      b = b.filter((it, i) => it !== t);
    } else {
     b = [...b, t];
    } 
      if(b.length === 12 ){
         break;
       }else{
         if(i === 12){
             i--;
         }
      }
   }

- Maneesh pandey

---

这个回答实际上并没有解决原帖提出的两个问题。解释为什么采用这种方法比他们当前的代码更高效可能会更有意义。 - JIntro

一些解释会让这个答案更好。 - isherwood

Answer 10

与最受欢迎的答案一样，我的解决方案没有实现 OP 对“最近 5 个选择”的引用，而是简单地“随机选择项目，直到所有项目都被选中，然后再重复”。这个解决方案不是递归的，也没有可能“在找到唯一名称之前一直循环”。它利用了 filter() 函数，因此避免了使用 for 循环。我认为从语法简洁性的角度来看，它是高效的。

const a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
let b = a;

const chooseName = () => {
  let name = b[Math.floor(Math.random() * b.length)]
  b = b.filter((v) => v !== name)
  if (b.length === 0) {
    b = a
  }
  return name
}

- RonH