获得多个玩家之间所有可能的纸牌排列

Question

我正在尝试获得 3 名玩家之间所有可能的 n 牌交易，其中每个玩家 i 恰好需要 n_i 牌，而一些玩家无法获得一些卡片数量。

例如，假设有4张牌：Ac,Jh,9d,2s，玩家N,E,S分别需要1,1,2张牌，但是N拿不到Ac, S 无法得到 Jh.

输入是n张牌的列表，每个位置和每张牌的限制：

List<Card> unplayedCards
Map<Position, Integer> numberOfCardsEachPlayerNeeds
Map<Card, List<Position>> possiblePositionsForCard

输出应该是可能交易的列表，所以

List<Map<Position, List<Card>>>

我正在用 Java 写作，但答案是哪种语言并不重要。

Answer 1

使用递归算法最容易做到这一点。 Python-类似伪代码：

function possible_deals(players, cards):
  output := []
  generate_deals(players, cards, 0, {}, output)
  return output

function generate_deals(players, cards, index, assignment, output):
  if index >= len(cards):
    output.append(assignment)
  else:
    card := cards[index]
    for player in players:
      if player doesn't have enough cards yet and player can have card:
        assignment[card] = player
        generate_deals(players, cards, index + 1, assignment, output)
        del assignment[card]

我们假设 assignment 和 output 的传递引用语义，以便递归函数调用可以修改它们。

output 列表中的每个条目都包含一张从纸牌到玩家的地图。由此，很容易重建手。

Answer 2

根据@Thomas 的回答制作了一个 Java 版本。

static List<Map<Position, CardsList>> getAllPossibleDeals(CardsList cards, Map<Position, Integer> cardsPerPosition,
                                                          Map<Card, List<Position>> positionsPerCard, List<Card> unplayedCardsOrderedByPossibilities) {

    List<Map<Position, CardsList>> possibleDeals = new ArrayList(); // all the deals
    Map<Position, CardsList> assignment = new HashMap<>(); // a single deal.
    generateDeals(cards, cardsPerPosition, positionsPerCard, possibleDeals, 0, assignment); 
    return possibleDeals;
}


private static void generateDeals(CardsList cards, Map<Position, Integer> cardsPerPosition, Map<Card, List<Position>> positionsPerCard,
                                  List<Map<Position, CardsList>> possibleDeals, int i, Map<Position, CardsList> assignment) {

    if (i >= cards.size()){
        Map<Position, CardsList> assignmentCopy = deepCopyMap(assignment);
        possibleDeals.add(assignmentCopy);
    }
    else {
        Card card = cards.get(i);
        for (Position pos : positionsPerCard.get(card)) {
            if (assignment.get(pos) == null || cardsPerPosition.get(pos) > assignment.get(pos).size()){
                // position can have the card
                assignment.computeIfAbsent(pos, k -> new CardsList()).add(card);
                generateDeals(cards, cardsPerPosition, positionsPerCard, possibleDeals, i+1, assignment);
                assignment.get(pos).remove(card);
            }
        }
    }
}

获得多个玩家之间所有可能的纸牌排列

getting all the possible permutation of cards between several players

algorithm

playing-cards