Алгоритм сортировки

Question

Мне нужно создать алгоритм сортировки, который будет сортировать карты на основе пар, так, например, если у вас есть 4JJQQ, он должен сортировать QQJJ4. Я пробовал много разных способов, но у меня, похоже, не получается правильно заказать заказ. У меня в основном есть массив карт, содержащих эту руку.

Answer 1

Если TYPE = {A, K, Q, J, A, 10..2} (в Java enum возможно) где А> K> Q> J> 10> ...> 2

Тогда это будет сделать это:

class Card implements Comparable<Card> { 
    public TYPE ty; 
    public Card(TYPE t) { 
    ty = t; 
    } 
    public int compareTo(Card card) { 
    return card.ty - ty; //you should rewrite this according to [1] rules 
    } 
} 

Сортировка:

Collections.sort(listOfCards); where listOfCards is a List<Card>. 

[1] http://www.javapractices.com/topic/TopicAction.do?Id=10

Answer 2

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

Если ваша основная проблема заключается в том, чтобы в основном сравнивать литералы, такие как J и цифры 4, то Counting Sort - ваше решение.

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

Advantage: Сортировка сортировки - это более быстрый алгоритм (в среднем, время O (n)), чем другие общие алготы, такие как Merge и Quicksort. Если у вас есть ограниченные возможные значения, я говорю, что вы его используете.

Теперь идет часть сортировки в «парах», что я не совсем понимаю. Не могли бы вы рассказать, каковы ожидаемые ответы на следующие тестовые примеры: "JJQJ4" и "JQ329"?

Типичные Counting сортировки может сортировать их как QJJJ4 и QJ932 (Нет понятия пар здесь)

Если ваш шаблон ответа не [пар] [болванка] каждый отсортированный в порядке убывания, вам нужно только изменить сортировку, чтобы сначала заполнить ровное количество карточек. Если доступные карты, оставшиеся для любого литерала, равны 1 или 0, он заполняет их в конце. Таким образом, ответ на моих тестовых случаях будет

JJQJ4 и QJ923.

Также оба ваших тестовых примера, похоже, тоже подходят.

---

Альтернатива:

Вы сказали, что вы хотите, чтобы пропустить того, чтобы сравнить оба литералов, когда ясно, что они являются парой.Могу я предложить использовать древовидное хранилище литералов. Таким образом, идея состоит в том, чтобы иметь центральный узел игрока с двумя детьми. Левый ребенок будет хранить вхождения пар, в то время как Right будет хранить особые.

Хранение литералов будет осуществляться в двоичном древе. Вставка литералов будет изменена.

Когда вы получаете 45JJQ,

1) Входной сигнал: 4. Процесс: сохранить 4 как rChld узла игрока

2) Вход: 5. Процесс: хранить 5 как rChld из 4

3) Вход: J. Процесс: хранить J как rChld из 5

4) Вход: J. Процесс: поскольку присутствует другой J, 5-> rChld: NULL. J хранится как lChld узла игрока (опять-таки, в двоичном древовидном режиме, т. Е. Если в lChld [Two Pairs] уже имеется буквальный текст, тогда J будет храниться как этот литерал слева или справа на основе того, больше или меньше).

5) Вход: Q. Процесс: сохранить Q как rChld из 5

Чтобы сравнить две руки, вы сначала просматриваете самую высокую карту в парах (самый правый ребенок не имеет детей). Вы также можете легко подсчитать количество пар. В общем двоичном дереве вам понадобится BFS или DFS. Но так как вы можете иметь максимум 2 пары, вы можете сделать это тривиально. Если значение lChld равно null, повторите поиск для высокой карты в rChild с уникальными картами.

Примечание: Если вы действительно делаете игру, похожую на покер, вам также могут понадобиться такие вещи, как 3. Это может быть размещено в узлах, сохраняя «вес» в левых дочерних элементах игрового узла. То есть, если J встречается дважды, вес равен 2, если он встречается трижды, вес равен 3 и так далее. Лучшим способом, чем вес, может быть использование binomial heaps.