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

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

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

			/* Случайное число между lower и higher включительно */
public static int rand(int lower, int higher) {
	return lower + (int)(Math.random() * (higher - lower + 1));
}

/* Выбрать M элементов из исходного массива. Клонируемый исходный 
* массив так, чтобы не уничтожить ввод */
public static int[] pickMRandomly(int[] original, int m) {
	int[] subset = new int[m];
	int[] array = original.clone();
	for(int j = 0; j < m; j++) {
		int index = rand(j, array.length - 1);
		subset[j] = array[index];
		array[index] = array[j]; //array[j] теперь "мертв"
	}
	return subset;
}
		

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»