得到几个玩家之间所有可能的牌的排列

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);
}
}
}
}