Напишите метод, тасующий карточную колоду

Обложка: Напишите метод, тасующий карточную колоду
2

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

Решение

Это очень популярная задача и известный алгоритм. Если вы еще не знакомы с решением, читайте дальше.

Давайте будем решать задачу «в лоб». Можно выбрать карты в произвольном порядке и поместить их в новую колоду. Фактически колода представляет собой массив, следовательно, нам нужен способ, позволяющий заблокировать отдельные элементы.

Исходная колода (до выбора 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 – Компанию»

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Что думаете?