Напишите метод, тасующий карточную колоду. Колода должна быть идеально перемешана. Перестановки карт должны быть равновероятными. Вы можете использовать идеальный генератор случайных чисел.
Решение
Это очень популярная задача и известный алгоритм. Если вы еще не знакомы с решением, читайте дальше.
Давайте будем решать задачу «в лоб». Можно выбрать карты в произвольном порядке и поместить их в новую колоду. Фактически колода представляет собой массив, следовательно, нам нужен способ, позволяющий заблокировать отдельные элементы.
Исходная колода (до выбора 4): [1] [2] [3] [4] [5]
/* Выбираем случайный элемент для помещения его в начало перетасованной колоды
* Помечаем элемент в оригинальной колоде как "заблокированный", чтобы
* не выбрать его снова */
Перемешанная колода (после выбора 4): [4] [?] [?] [?] [?]
Исходная колода (после выбора 4): [1] [2] [3] [X] [5]
Если мы пометим элемент [4], что помешает выбрать его еще раз? Один из способов – поменять местами «мертвый» ([4]) и первый элементы колоды:
Исходная колода (до выбора 4): [1] [2] [3] [4] [5]
/* Выбираем случайный элемент для перемещения его в начало перетассованной колоды
* Существует элемент 1, который заменит выбранный элемент. */
Перемешанная колода (после выбора 4): [4] [?] [?] [?] [?]
Исходная колода (после выбора 4): [X] [2] [3] [1] [5]
/* Выбираем случайный элемент для перемещения его в начало
* перетасованной колоды. Есть элемент 2, который заменит только что
* выбранный элемент */
Перетасованная колода (после выбора 3): [4] [3] [?] [?] [?]
Исходная колода (после выбора 3): [X] [X] [2] [1] [5]
Алгоритм проще реализовать для ситуации, когда «мертвы» первые k карт, чем для ситуации, когда, например, «мертвы» третья, четвертая и девятая карты. Оптимизировать алгоритм можно, объединив перемешанную и исходную колоды вместе.
Исходная колода (до выбора 4): [1] [2] [3] [4] [5]
/*Выбираем случайный элемент между 1 и 5 и меняем его местами с 1.
* В этом примере мы выбрали элемент 4.
* После этого элемент 1 - "мертв" */
Исходная колода (после выбора 4): [4] [2] [3] [1] [5]
/* Элемент 1 "мертв". Выбираем случайный элемент для замены с
* элементом2. В этом примере пусть мы выберем элемент
* 3.*/
Исходная колода (после выбора 3): [4] [3] [2] [1] [5]
/* Повторяем. Для всех i между 0 и n-1 меняем местами случайный элемент j
* (j >= i, j < n) и элемент i. */
Этот алгоритм легко реализовать итеративно:
public void shuffleArray(int[] cards) {
int temp, index;
for (int i = 0; < cards.length; i++) {
/*Карты с индексами от 0 до i-1 уже были выбраны
* (они перемещены в начало массива), поэтому сейчас мы
* выбираем случайную карту с индексом, больше или равным i
* */
index = (int) (Math.random() * (cards.length - i)) + i;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
}
Подобный алгоритм можно придумать и самостоятельно, он достаточно часто встречается на собеседовании. Перед интервью стоит убедиться, что вы понимаете механизм его работы.
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»