getting all the possible permutation of cards between several players

Question

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.

Answer 1

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.