I am trying to get all the possible deals of n
cards between 3 players, where each player i
need exactly n_i
cards and some of the players can not get some of the cards.
For example, assume there are 4 cards: Ac,Jh,9d,2s
and player N,E,S
needs 1,1,2
cards respectively, but N
can't get the Ac
, and S
can't get the Jh
.
The input is the list of n
cards, and the restrictions for each position and for each card:
List<Card> unplayedCards
Map<Position, Integer> numberOfCardsEachPlayerNeeds
Map<Card, List<Position>> possiblePositionsForCard
The output should be a list of the possible deals so
List<Map<Position, List<Card>>>
I am writing in Java, but it is not important which language the answer is.
It's easiest to do this with a recursive algorithm. Python-like pseudocode:
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]
We're assuming pass-by-reference semantics for assignment
and output
so that recursive function calls can modify these.
Each entry in the output
list contains a map from cards to players. From this, it's easy to reconstruct the hands.