Карьера программиста, или Cracking Coding Interview

Напишите метод, генерирующий случайную последовательность m целых чисел из массива размером n. Все элементы выбираются с одинаковой вероятностью.

Задание
Напишите метод, генерирующий случайную последовательность m целых чисел из массива размером n. Все элементы выбираются с одинаковой вероятностью.

Решение
Первое, что приходит в голову — выбрать случайные элементы из массива и поместить в новый массив. Но, что если мы выберем один и тот же элемент дважды? В идеале, нам нужно «сократить» массив так, чтобы выкинуть выбранный элемент. Но уменьшение массива достаточно трудоемкая операция, поскольку требует смещения элементов.

Вместо того чтобы сокращать (сдвигать) массив, можно поставить элемент (поменять элементы местами) в начало массива, и «запомнить», что теперь массив начинается с элемента j. Если элемент subset[0] становится элементом array[k], то мы должны заменить элемент array[k] первым элементом в массиве. Когда мы переходим к элементу subset[1], то подразумеваем, что элемент array[0] «мертв», и выбираем случайный элемент y из интервала от 1 до array.size(). Теперь subset[1] = array[y] и array[y] = array[1]. Элементы 0 и 1 «мертвы», а subset[2] выбирается в диапазоне от array[2] до array[array.size()] и т. д.

1 /* Случайное число между lower и higher, включительно */
2 public static int rand(int lower, int higher) {
3 return lower + (int)(Math.random() * (higher — lower + 1));
4 }
5
6 /* Выбрать M элементов из исходного массива. Клонируем исходный
7 * массив так, чтобы не уничтожить ввод */
8 public static int[] pickMRandomly(int[] original, int m) {
9 int[] subset = new int[m];
10 int[] array = original.clone();
11 for (int j = 0; j < m; j++) {
12 int index = rand(j, array.length — 1);
13 subset[j] = array[index];
14 array[index] = array[j]; // array[j] теперь «мертв»
15 }
16 return subset;
17 }