How can I efficiently select random items from an array without repetition, especially when the array is constantly being modified?

Efficient Random Selection from an Array

Introduction

Randomly selecting an item from an array without repetition is a common programming task. However, if the pool of items is constantly being modified, ensuring efficiency becomes crucial.

Question

A developer has implemented a function to randomly select an item from an array while maintaining a list of recent choices to avoid repetition. However, they express concerns about its efficiency and inquire if there is a more optimal approach.

Answer

1. Recursion Clarification

The provided code indeed appears to be a recursive function. Recursion involves a function calling itself, which can lead to inefficiencies in certain scenarios.

2. Efficiency Improvement

To improve efficiency, consider the following alternative approach:

1. Create a copy of the original array. This ensures that the original array remains intact.
2. Define a function that randomly selects an item from the copy.
3. When the copy is depleted, reset it by creating a new copy from the original array.

Code Implementation:

<code class="javascript">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']);</code>

Explanation:

This approach isolates the random selection logic from the code responsible for managing the array of recent choices. As a result, efficiency is improved because the random selection occurs only once per run of the chooser function.

By resetting the copy whenever it is depleted, the function guarantees that all items have an equal chance of being selected. This eliminates the potential issue of the code getting stuck in an infinite loop trying to find a "unique" name.

The above is the detailed content of How can I efficiently select random items from an array without repetition, especially when the array is constantly being modified?. For more information, please follow other related articles on the PHP Chinese website!