algorithmplaying-cards

getting all the possible permutation of cards between several players


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.


Solution

  • 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.