Эффективные способы сортировки колоды реальных карт

Ответ 1

Я думаю, что для вас это самый быстрый способ. Я думаю, что есть даже некоторые видео Youtube, показывающие, как люди делают это с обычной покерной колодой.

Вы проходите через колоду и кладете все карты меньше 100 на левую кучу, все больше на правой куче. Затем вы сначала берете груды, сначала глубину (так что вы не имеете слишком много кучек сразу). На некотором пороге (возможно, около 5 карт) вы просто сортируете "в руке" (по-видимому, похоже на сортировку вставки). Наконец, вы складываете сваи вместе.

Вы также можете сделать сортировку слияния: разделите кучу на две части, сначала запишите глубину, до тех пор, пока вы не достигнете двух грудов по 5 карт. Сортируйте эти две сваи "в руке", затем положите их лицом вверх бок о бок. Объедините их в кучу результата, всегда ставя нижнюю из отображающих карточек в кучу результата. Вы можете видеть, какие свай уже отсортированы, оставив их лицом вверх. Обязательно всегда объединяйте сваи одинакового размера, в противном случае переходите к разделению следующей несортированной кучи.

Редактирование: сортировка по методу "радикс" тоже может быть хорошей: поместите карты в десять свай по их последней цифре, соедините эти сваи по порядку. Затем положите карты на десять свай по их второй до последней цифре, соедините их вместе в порядке еще раз. Наконец, поместите их в груды своей третьей до последней цифрой (в соответствии с вашим описанием, то есть первой цифрой) и соедините их вместе. В конце концов, это может быть проще всего, и это O (n) (вам нужно три прохода через колоду).

Ответ 2

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

Есть трюки, чтобы ускорить сортировку ковша. Большую часть времени в сортировке человеческого ведра затрачивается на вычисление ведра для следующего предмета. Вы можете попробовать два трюка. Во-первых, вы можете сортировать ведро по цифре, что, я думаю, называется сортировкой radix, так что вам никогда не придется сравнивать числа. На первом этапе используются три ведра, которых не так много, но они могут быть в порядке. Второй этап - "основная" работа с десятью ведрами. На третьем этапе вы сортируете десять пронумерованных карточек, а здравый смысл предлагает сортировку вставки. Но даже на этом этапе сортировка радикса может ускорить работу, хотя в каждом ковше только одна карта. Конечно, вы не должны использовать "ведра" с четырьмя сторонами, а просто груды карточек на столе. Вы бы использовали только метод bucket для цифры единиц, если легко подметать карты по порядку. Возможно, для средней ступени слот с тремя сторонами будет работать лучше, чем открытая куча карт.

Второй трюк - обозначить местоположения в таблице от 0 до 9, чтобы вы могли быстрее найти нужную кучу. Этикетки можно наклеить на стол, чтобы вы могли их повторно использовать.

Я не уверен, что эта конкретная стратегия сортировки в виде корзины является лучшей. Дело в том, что сортировка ковша является наиболее распространенным методом сортировки промежуточных значений и, вероятно, лучше всего подходит для больших колод карт. Есть несколько вариантов попробовать, и вы должны немного поэкспериментировать, чтобы увидеть, какой из них лучше всего работает.

Ответ 3

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

Например, было ли максимум 100 карт, пронумерованных 1-100, представьте, что ваша рабочая поверхность разделена на прямоугольную сетку 10 x 10; то, как только каждая карта обрабатывается, введите, например, карту 67 в 7-й столбе 6-й строки. Как только все карты будут выложены, подберите их в порядке.

Это работает только в том случае, если ваша рабочая поверхность достаточно большая, чтобы содержать все карты, но если они являются нормальным размером игральной карты, и у вас есть хороший большой стол, он должен уметь справляться с 200, о которых вы упоминаете, тем более, что вы могут легко пересекаться с "ячейками", и этот метод все еще работает.

Для меня это подход, который в наибольшей степени использует тот факт, что это проблема в физическом пространстве, а не в битах - каждый физический объект обрабатывается только дважды (один раз, чтобы поместить его на место, один раз, чтобы забрать его), потому что для алгоритма с участием физических объектов, перемещение их вокруг имеет гораздо большую стоимость, чем мышление о том, что делать.

Ответ 4

Эрик,

Не уверен, что вы все еще выполняете заказы на физические колоды карт, но я изучал это (сортировка карт, сортировка игл, сортировка machiens и т.д.) и наткнулась на ваш пост. Если вы этого не сделаете, я надеюсь, что кто-то другой найдет его полезным/полезным.

Если у вас есть возможность использовать дырокол и изменить край колоды карт, то для упорядочивания всей сваи в log2 (#of-карточках) можно использовать метод сортировки. Таким образом, для ~ 200 карт потребуется 8 операций.

Один из способов, который я нашел, работал хорошо:

1.) Закажите колоду так, как вы хотите, и дайте каждой карте #.

2.) Преобразуйте этот # в двоичный файл на длину log2 (количество карточек).     например log2 (216) ~ 8, тогда вам понадобится только 8 мест... так что 0x0 станет 00000000

3.) Enode каждая карта с двоичным представлением, как показано на рисунке ниже

ПИК

4.) Обрежьте 1, как на карточке 1 ниже (правый или LSB обрезается), вторая до последней на карте 2 также обрезается...

5.) Возьмите гвоздь, или вязальную иглу или прямую вешалку и т.д.... упаковать колоду вместе (неупорядоченно) с выровненными отверстиями

6.) вставьте иглу через правое отверстие на всей колоде (или lsb в двоичном формате). поднимите иглу и позвольте картам, которые не имеют кольца на этой вкладке (вы разрезаете ее), попадают в коробку. Переместите карты, зацепившиеся за иглу, в передней части колоды. ** НЕ ИЗМЕНЯЙТЕ ЗАКАЗ ОТ НЕПРЕРЫВНЫХ КАРТ, ПОДТВЕРЖДАЯ ОТДЕЛЬНЫЕ КАРТЫ. держите колоду в коробке с короткими фитингами или что-то подобное

7.) Снова упакуйте колоду, на этот раз используйте иглу на ранее используемом соседнем отверстии (второе справа). сделайте то же самое, пусть неприкрепленные/невыделенные карты попадут в коробку и повторите.

8.) w/8 операций вся колода должна быть отсортирована... Надеюсь, это поможет кому-то

вот как это работает: первая операция (этап 6) перемещает все нечетные объекты на фронт, например. ставит 1 перед 2, 3 перед 4 и т.д.

вторая операция перемещается (1/2 перед 3/4) и 5/6 перед 7/8. третья операция перемещается 1/2/3/4 перед 5/6/7/8 и 9/10/11/12 перед 13/14/15/16.. четвертая операция перемещается 1/2/3/4/5/6/7/8 перед 9/10/11/12/13/14/15/16/ и т.д... последний ход занимает ~ одну половину колоды и помещает ее перед другой... и это приводит к полностью упорядоченной колоде в минимальном количестве ходов.

Cheers, Джереми

Ответ 5

Я думаю, что подсчет сортировки вместе с вашим методом сортировки вставки может работать хорошо: сканировать их и ставить их сначала, затем два и скоро.

Это может показаться большой работой, так как ваши карты пронумерованы от 1 до более 200, но я думаю, что в этом случае все будет много работать. Вы можете ускорить процесс, выполнив сразу несколько карт, что не должно быть слишком сложным: сначала сканируйте те, два и три (и больше, если вы за это), и поместите их в соответствующие позиции ( в сочетании с "сортировкой вставки", поэтому вам не нужно оставлять пустое пространство между картами.)

Ответ 6

Я столкнулся с этим сообщением, потому что хотел быстро отсортировать обычную колоду из 52 игральных карт. Небольшое экспериментирование предполагает, что я могу сортировать всю колоду примерно в 1:30, используя алгоритм обработки каждой карты в кучу для каждого костюма, а затем вставку сортировать по одному костюму за раз (практически без практики, поэтому я уверен, что это может быть сделано быстрее с практикой).

Я пробовал несколько разных подходов, включая красно-черный раскол, а затем раскалывал красных и черных в свои собственные костюмы, а затем занимался сортировкой по костюмам, но это было заметно медленнее. Я также попытался разбить каждый костюм на 2-7,8-A, чтобы увидеть, была ли сортировка вставки на небольших группах карт быстрее, но она также заметно медленнее. Таким образом, мой урон не тратит ваше время с чрезмерной рекурсией, чтобы сделать брокер.

Экстраполируя этот метод на ваши карты, кажется, что наилучшим подходом является использование карт в ведрах, которые вам легко отсортировать сразу (10 или 20 карт, возможно, так как легко понять в каком ковше они входят), затем введите сортировку в ведрах. Предположительно, вы должны иметь возможность сортировать свои 216 карточные колоды примерно через 6-7 минут.