Генерация сочетания k элементов из множества n

#javascript #алгоритм

Как можно сгенерировать случайное сочетание в JavaScript?

То есть k различных элементов из множества размера n.

(например, k различных чисел из множества {1, ..., n})
    

Ответы

Ответ 1

Чтобы сгенерировать случайное сочетание размера k из множества размера n можно сделать
k шагов, на каждом из которых:


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


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



let numberElements = 10;
let combinationSize = 6;
// для примера сгенерируем сочетание из множества {0, 1, ..., n-1}
let array = [...Array(numberElements).keys()];

let combination = [];
while (combination.length < combinationSize) {
  // выбираем случайный элемент массива и добавляем его к сочетанию
  let randomIndex = Math.floor(Math.random() * array.length);
  let randomElement = array[randomIndex];
  combination.push(randomElement);

  // удаляем выбранный элемент из массива
  array[randomIndex] = array[array.length - 1];
  array.pop();
}

// результат --- массив combination
console.log(combination)




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

Должно работать за O(размер сочетания). Получающиеся сочетания имеют равномерное
распределение, так как вероятность получить размещение a_1 ... a_k равна (ξ_i ­— элемент,
выбранный на i-ом шаге)



— зависит только от n и k, а каждому сочетанию соответствует одинаковое (k!) число
размещений.


Ответ 2

В зависимости от номера i выбираемого элемента, общее количество генераций в среднем
равно n / (n - i), из них i / (n-i) ≈ i / n лишних.
Суммарное количество лишних генераций примерно равно (k-1)(k-2) / 2n ≈ k2 / 2n.

В зависимости от соотношения k и n, можно рекомендовать различные стратегии.


Если k2 < 2n, то генерировать индексы копируемых элементов (с проверкой повторов).
Если (n-k)2 < 2n, то создать копию исходного массива и генерировать индексы удаляемых
элементов.
В остальных случаях - перетасовать исходный массив (обменивая каждый элемент массива
со случайно выбранным) и отобрать первые k элементов.