Самый элегантный способ расширить карточные масти

Question

Я храню 4-карточные руки таким образом, чтобы обрабатывать руки с разными мастями одинаково, например ::10000

9h 8h 7c 6c

совпадает с

9d 8d 7h 6h

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

9A 8A 7B 6B

У меня вопрос: какой самый элегантный способ превратить последнее в список первых? Например, если входное значение равно 9A 8A 7B 6B, выходное значение должно быть:

9c 8c 7d 6d
9c 8c 7h 6h
9c 8c 7s 6s
9h 8h 7d 6d
9h 8h 7c 6c
9h 8h 7s 6s
9d 8d 7c 6c
9d 8d 7h 6h
9d 8d 7s 6s
9s 8s 7d 6d
9s 8s 7h 6h
9s 8s 7c 6c

У меня есть некрасивый код, который делает это в каждом конкретном случае в зависимости от количества уникальных мастей. Это не будет масштабироваться до рук с большим количеством карт. Также в ситуации, как:

7A 7B 8A 8B

будет иметь дубликаты, поскольку в этом случае A=c и B=d совпадают с A=d и B=c.

Какой элегантный способ эффективно решить эту проблему? Я пишу на C, но могу преобразовать код более высокого уровня в C.

Answer 1

Есть только 4 масти, поэтому пространство возможных замен действительно мало - 4! = 24 случая. В этом случае я не думаю, что это стоит того, чтобы попытаться придумать что-то особенно умное.

Просто проанализируйте строку, например "7A 7B 8A 8B", посчитайте количество различных букв в ней и на основе этого числа сгенерируйте замены на основе предварительно вычисленного набора замен.

1 letter -> 4 possible substitutions c, d, h, or s
2 letters -> 12 substitutions like in Your example.
3 or 4 letters -> 24 substitutions.

Затем отсортируйте набор замен и удалите дубликаты. Вы должны отсортировать токены в каждой строке, например "7c 8d 9d 9s", а затем отсортировать массив строк для обнаружения дубликатов, но это не должно быть проблемой. Хорошо также отсортировать шаблоны типа «7A 7B 8A 8B» (токены типа «7A», «8B» расположены в порядке возрастания).

EDIT:

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

Например, для строки «7A, 7B, 8A, 8B» с буквой A связан набор {7, 8}, и тот же набор связан с буквой B. Затем необходимо найти идентичные наборы, связанные с разными буквами. В большинстве случаев эти наборы будут иметь только один элемент, но они могут иметь два, как в примере выше. Письма, связанные с одним и тем же набором, являются взаимозаменяемыми. Вы можете иметь следующие ситуации

1 letter no duplicates -> 4 possible substitutions c, d, h, or s
2 letters no duplicates -> 12 substitutions.
2 letters, 2 letters interchangeable (identical sets for both letters) -> 6 substitutions.
3 letters no duplicates -> 24 substitutions.
3 letters, 2 letters interchangeable -> 12 substitutions.
4 letters no duplicates -> 24 substitutions.
4 letters, 2 letters interchangeable -> 12 substitutions.
4 letters, 3 letters interchangeable -> 4 substitutions.
4 letters, 2 pairs of interchangeable letters -> 6 substitutions.
4 letters, 4 letters interchangeable -> 1 substitution.

Answer 2

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

Найдите, сколько уникальных мастей существует в руке. Затем сгенерируйте все возможные перестановки с этими множеством элементов из реальных мастей [c, d, h, s]. Наконец, просмотрите каждую перестановку мастей и присвойте каждой неизвестной букве [A, B, C, D] в руке переставленные значения.

Следующий код на Ruby берет данную руку и генерирует все перестановки мастей. Самая тяжелая работа выполняется здесь методом Array.permutation(n), который должен значительно упростить работу соответствующей C-программы.

# all 4 suits needed for generating permutations
suits = ["c", "d", "h", "s"]

# current hand
hand = "9A 8A 7B 6B"

# find number of unique suits in the hand. In this case it's 2 => [A, B]
unique_suits_in_hand = hand.scan(/.(.)\s?/).uniq.length

# generate all possible permutations of 2 suits, and for each permutation
# do letter assignments in the original hand
# tr is a translation function which maps corresponding letters in both strings.
# it doesn't matter which unknowns are used (A, B, C, D) since they 
# will be replaced consistently.
# After suit assignments are done, we split the cards in hand, and sort them.
possible_hands = suits.permutation(unique_suits_in_hand).map do |perm|
   hand.tr("ABCD", perm.join ).split(' ').sort
end

# Remove all duplicates
p possible_hands.uniq

Вышеприведенный код выводит

9c 8c 7d 6d
9c 8c 7h 6h
9c 8c 7s 6s
9d 8d 7c 6c
9d 8d 7h 6h
9d 8d 7s 6s
9h 8h 7c 6c
9h 8h 7d 6d
9h 8h 7s 6s
9s 8s 7c 6c
9s 8s 7d 6d
9s 8s 7h 6h

Answer 3

#include <stdio.h>
#include <stdlib.h>

const int RANK = 0;
const int SUIT = 1;

const int NUM_SUITS = 4;

const char STANDARD_SUITS[] = "dchs";
int usedSuits[] = {0, 0, 0, 0};

const char MOCK_SUITS[] = "ABCD";

const char BAD_SUIT = '*';

char pullSuit (int i) {
  if (usedSuits [i] > 0) {
    return BAD_SUIT;
  }
  ++usedSuits [i];
  return STANDARD_SUITS [i];
}

void unpullSuit (int i) {
  --usedSuits [i];
}

int indexOfSuit (char suit, const char suits[]) {
  int i;
  for (i = 0; i < NUM_SUITS; ++i) {
    if (suit == suits [i]) {
      return i;
    }
  }
  return -1;
}

int legitimateSuits (const char suits[]) {
  return indexOfSuit (BAD_SUIT, suits) == -1;
}

int distinctSuits (const char suits[]) {
  int i, j;
  for (i = 0; i < NUM_SUITS; ++i) {
    for (j = 0; j < NUM_SUITS; ++j) {
      if (i != j && suits [i] == suits [j]) {
        return 0;
      }
    }
  }
  return 1;
}

void printCards (char* mockCards[], int numMockCards, const char realizedSuits[]) {
  int i;
  for (i = 0; i < numMockCards; ++i) {
    char* mockCard = mockCards [i];
    char rank = mockCard [RANK];
    char mockSuit = mockCard [SUIT];
    int idx = indexOfSuit (mockSuit, MOCK_SUITS);
    char realizedSuit = realizedSuits [idx];
    printf ("%c%c ", rank, realizedSuit);
  }
  printf ("\n");
}

/*
 * Example usage:
 * char** mockCards = {"9A", "8A", "7B", "6B"};
 * expand (mockCards, 4);
 */
void expand (char* mockCards[], int numMockCards) {
  int i, j, k, l;
  for (i = 0; i < NUM_SUITS; ++i) {
    char a = pullSuit (i);
    for (j = 0; j < NUM_SUITS; ++j) {
      char b = pullSuit (j);
      for (k = 0; k < NUM_SUITS; ++k) {
        char c = pullSuit (k);
        for (l = 0; l < NUM_SUITS; ++l) {
          char d = pullSuit (l);
          char realizedSuits[] = {a, b, c, d};
          int legitimate = legitimateSuits (realizedSuits);
          if (legitimate) {
            int distinct = distinctSuits (realizedSuits);
            if (distinct) {
              printCards (mockCards, numMockCards, realizedSuits);
            }
          }
          unpullSuit (l);
        }
        unpullSuit (k);
      }
      unpullSuit (j);
    }
    unpullSuit (i);
  }
}

int main () {
  char* mockCards[] = {"9A", "8A", "7B", "6B"};
  expand (mockCards, 4);
  return 0;
}

Answer 4

Представляет масти как разреженные массивы или списки, числа как индексы, стрелки как ассоциативные массивы

В вашем примере

H [A [07080000] B [07080000] C [00000000] D [00000000]] (место для четырех карт)

Чтобы получить «настоящие» руки, всегда применяйте 24 перестановки (фиксированное время), поэтому вам не нужно заботиться о том, сколько карт имеет ваша рука A, B, C, D -> c, d, h, s со следующим "трюком"> хранить всегда в алфавитном порядке>

H1 [c [xxxxxx] d [xxxxxx] s [xxxxxx] h [xxxxxx]]

Так как Руки являются ассоциативными массивами, дублированные перестановки не генерируют две разные выходные руки.