Генерации сочетания в JavaScript

Чтобы сгенерировать случайное сочетание размера 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!) число размещений.