Как эффективно случайным образом выбирать элемент массива без повторов?

Я знаю, что этот вопрос существует во многих обличьях, но я не смог найти ответ, связанный с моей конкретной проблемой эффективности.

У меня есть код ниже, который работает отлично.

У меня есть массив из 10 элементов, из которого я случайно выбираю элемент (при нажатии клавиши ввода). Код хранит массив из 5 самых последних вариантов, которые нельзя выбрать случайным образом (чтобы избежать слишком много повторений с течением времени).

Если функция selectName () изначально выбирает имя, которое использовалось в последних 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); 

Всякий раз, когда элемент выбран, переместите его в обратную сторону массива и произвольно выберите из среза исходного массива array.slice(0, -5) .

 var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"]; var chooseName = function () { var unique = true; 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); 

EDIT: Это также имеет побочный эффект от того, что какие-либо переменные не совпадают с списком несправедливого недостатка, которого они не будут рассматривать в первых N вызовах. Если это проблема для вас, возможно, попробуйте сохранить статическую переменную где-нибудь, чтобы отслеживать размер используемого fragmentа и максимально использовать его в 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 () { var unique = true; num = Math.floor(Math.random() * a.length - N); N = Math.min(N + 1, B); name = a.splice(num,1); a.push(name); } 

Мне нравится комментатор @ Идея Юрия Галантера о выборе элементов случайным образом, пока все не будут приняты, и только тогда повторяется, так что вот реализация:

 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. 

Я рекомендую вам использовать 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); 

Когда вы создаете экземпляр Shuffler, дайте ему массив в качестве параметра. Он создаст копию массива, и каждый раз, когда будет вызываться next (), он вернет случайный элемент из копии и удалит его из массива копий, чтобы повторы не были возможны.

 var Shuffler = function(a) { var aCopy = [], n = 0; // Clone array for (n=0; n 

Да, это рекурсивно, и поскольку оно не уменьшает состояние, оно теоретически может продолжаться вечно.

Я предполагаю, что изменение массива недопустимо, так как в противном случае вы могли бы просто удалить недавние варианты из массива и оттолкнуть их обратно в качестве недавнего переполнения буфера выбора.

Вместо этого: исключайте элементы буферизации в конце массива из выделения. (Buffersize начинается с 0 и увеличивается до вашего предустановленного буферизамакса, когда в буфер добавляются последние варианты.) Когда вы делаете выбор, вы сравниваете его с вашими избранными вариантами bufffersize. Если вы найдете совпадение, вы выбираете вместо этого исключенный элемент.

Очевидно, что до сих пор неэффективна необходимость проверять каждый недавний выбор в буфере, чтобы избежать совпадения. Но у него есть эффективность, позволяющая избежать возможной рекурсии.

Эта работа как прелесть для меня без повторения.

  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; } } 
  • Как передать данные json POST в метод Web API как объект?
  • Преобразование эпохи UTC в локальную дату
  • Имя свойства объекта как число
  • Что делает три точки в ReactJS
  • Почему typeof x never 'number', когда x приходит из функции prompt?
  • Уведомление HTML5 не работает в Mobile Chrome
  • Используйте базовую аутентификацию с помощью jQuery и Ajax
  • Конкатентные скрипты в порядке с Gulp
  • стрелки и
  • В запрошенном ресурсе нет заголовка «Access-Control-Allow-Origin» - при попытке получить данные из REST API
  • Проверьте соответствие строки регулярному выражению в JS
  • Interesting Posts

    Как запустить экземпляры EC2 и загрузить / запустить сценарий запуска для каждого из них?

    Как обмениваться фотографиями между двумя MacBook Pro по беспроводной сети?

    JavaFX Как установить фоновое изображение сцены

    Служба DNS Google: общедоступный DNS Google

    C # Подключение через прокси

    Как реализовать пользовательскую таблицу представления таблицы Заголовки и нижние колонтитулы с раскадровки

    Ограничить дату в jquery datepicker на основе другого datepicker или текстового поля

    С Rails 4 Model.scoped устарел, но Model.all не может его заменить

    Макрос для экспорта таблиц MS Word в листы Excel

    Ошибки консоли. Не удалось загрузить ресурс: net :: ERR_INSECURE_RESPONSE

    Консоль менеджера пакетов Enable-Migrations CommandNotFoundException только в конкретном проекте VS

    ProgressDialog не отображается, когда AsyncTask.get () называется

    Рекомендации по копированию файлов с Maven

    Как узнать, почему сбой на удалении файлов на Java?

    Изменение цвета кнопки переполнения на ActionBar

    Давайте будем гением компьютера.