Я делаю класс Deck для программы на C++. У него должно быть два метода: один — снять карту с верха колоды, другой — перетасовать колоду. Меня беспокоит последнее.
Карты представлены целыми числами от 1 до 52 включительно. Каков самый быстрый алгоритм для перетасовки колоды (при условии «хорошего» уровня случайности)?
Если вы хотите реализовать перетасовку самостоятельно, воспользуйтесь очень простым, но функциональным алгоритмом перетасовки: Fisher – Йейтс перемешивает.
Чтобы перетасовать массив a из n элементов:
for i from n − 1 downto 1 do j ← random integer with 0 ≤ j ≤ i exchange a[j] and a[i]
Конечно, в стандартной библиотеке C++ также реализованы подобные вещи, такие как std::random_shuffle, включенный через заголовок <algorithm>.
std::random_shuffle является перетасовкой Фишера-Йейтса.)
- person Amber; 02.11.2010
for i from n − 1 downto 1: Случайно ли, что a[0] имеет высокую вероятность того же значения? почему не downto 0?
- person Han; 19.04.2016
a[0] можно поменять местами в любой итерации цикла, если j = 0. Если бы i было равно нулю, то j также должно было быть равно нулю (поскольку первая строка тела цикла установила бы j в случайное целое число, меньшее или равное нулю), что никак не изменило бы порядок.
- person Amber; 20.04.2016
Используйте std::random_shuffle, чтобы перетасовать колоду.
std::random_shuffle
http://www.cplusplus.com/reference/algorithm/random_shuffle/
