Составьте список списков, сортируемых по частоте встречаемости

Question

Настройка

У меня есть список пар целых чисел: ((1,2), (1,3), (2,5), (1,6), (2,8), (9,8), (8,11) и т. Д.).Внутри данной пары числа должны быть разными, но при рассмотрении списка в целом существует много повторов.

Хотя эта информация не имеет прямого отношения к проблеме, каждое число представляет карту из колоды (и составляет от 1 до 52 включительно), а каждая пара представляет одну из возможных карт игрока.

Проблема

Мы хотим отсортировать эти пары чисел таким образом, чтобы на первом месте были пары, содержащие наиболее часто встречающиеся карточки в списке.Затем эти пары упорядочены по 2-му числу в порядке возрастания.Затем мы повторяем процесс, используя оставшиеся пары в списке.Связи разрываются, используя правило, что меньшие числа идут первыми.Давайте сделаем пример, используя список сверху:

1. Числа 1, 8 и 2 каждый появляются в списке 3 раза, и ни один номер не появляется более 3 раз.Следовательно, есть 3 путевые ничьи и 1 победа.Мы строим первую часть списка следующим образом:

   (1,2)
   (1,3)
   (1,6)
   

2. Остальные элементы списка теперь (2,5), (2,8), (9,8),(8,11).8 появляется в 3 раза, больше, чем любое другое число, следовательно, 8 побед.Мы продолжаем наш список следующим образом:

   (1,2)
   (1,3)
   (1,6)
   (2,8) <-- Note 2 is the smallest of the "other" numbers amongst the 8 group
   (9,8)
   (8,11)
   (2,5) <-- This gets added in step 3, but since there is only 1 left we add it now
   

Критерии ответа

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

В частности:

• Какой объект коллекций следует использовать для представления как пар, так и общего списка?
• Должен ли я получить счетчики для каждого целого числа один раз в начале алгоритма, а затем обновить их, вычитая по мере их использования?Или я должен повторять счет после каждого прохода?Первый кажется более эффективным.
• Как лучше всего выполнить сортировку по «другому» числу в паре?
• Как насчет сортировки, когда возникают связи?

Спасибо за ваш вклад.

Answer 1

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

public class CardAndPairs implements Comparable<CardAndPairs> {
    Card card;
    List<Pair> pairs;

    public CardAndPairs(Card card, Set<Pair> allPairs) {
       this.card = card;
       pairs = new HashSet<>();
       for (Pair pair : allPairs) 
         if (pair.contains(card))
           pairs.add(pair);
       // You could then reorder "pairs" by the value of the other card
       // ... see below
    }

    @Override
    public int compareTo(CardAndPairs other) {
       int diff = pairs.size() - other.pairs.size();
       if (diff > 0)
          return 1;
       if (diff == 0)
          return card.compareTo(other.card);
       return 1;
    }
}

Затем вы можете поместить CardAndPairs для 52 карт в Список и автоматически отсортировать их (неявно используя compareTo) с помощью Collections.sort(list).

Чтобы отсортировать пары в пределах заданного CardAndPairs в конструкторе выше, он становится немного сложным, чтобы сделать это способом Java. Вместо того, чтобы использовать просто Pair, вы должны определить подкласс, а не реализовать Comparable:

public class PairWithGivenCard 
          extends Pair implements Comparable<PairWithGivenCard> {
   Card givenCard;
   Card otherCard;

   public PairWithGivenCard(Card givenCard, Pair pair) {
      this.givenCard = givenCard;
      for (Card card : pair) // or however you get the cards from pair
         if (card != givenCard)
            otherCard = card;
   }

   @Override
   public int compareTo(PairWithGivenCard otherPair) {
      // It might be a good idea to throw 
      //   some exception if givenCard != otherPair.givenCard
      return otherCard.compareTo(otherPair.otherCard);
   }
}

Затем вам потребуется изменить List<Pair> pairs на List<PairWithGivenCard> pairs в конструкторе CardAndPairs. И когда вы добавляете пару в список, вам нужно будет сделать pairs.add(new PairWithGivenCard(card, pair)) вместо pairs.add(pair). Наконец, вы просто вызываете Collections.sort(pairs) в конце конструктора CardAndPairs.