Dividing distinguishable cards into distinguishable hands where some hands cannot contain some cards

Question

I am making a computer program to play cards, for this algorithm to work I need to deal cards out randomly. However, I know that some people cannot have some cards due to the rules of the card game.

To elaborate on this, imagine we have 3 players: a, b and c. Also, there are 4 cards left to divide: 1, 2, 3 and 4. I know from c that he cannot have card 1 or card 2, I know from player a that he cannot have card 3. Each player is listed below with their corresponding possible cards.

a    b    c
1    1
2    2
     3    3
4    4    4

Also, I know that player a must receive 1 card, player b must receive 2 and player c must receive 1 card (for a total of 4 cards). Note, that it does not matter in which order a player receives his cards.

My Question: Is there some algorithm that can deal the cards out randomly (with arbitrary amounts of cards and 3 players) such that each possible deal is equally likely?

My attemps on solving this problem: First, I enlisted each possible solution (note that switching the cards around in the middle column doesn't influence the relative chances of the possibilities).

a    b    c
1   2 3   4
1   2 4   3
2   1 3   4
2   1 4   3
4   1 2   3

And then I noticed that every algorithm that I could think of did not sample the above possibilities with equal chances. I could, however, come up with one algorithm which is to generate a random partition of 1, 2, 3 and 4 and check if it is valid. If its not I generate a random partition again and check it, and so on. Altough this gives me a random sample where all options are equally likely, as we move on to more and more cards this algorithm takes up a lot of time. I have had no succes on finding speedups or different algorithms to solve this problem.

Answer 1

Since each card must be dealt, this can be done recursively.

Let $P_i=\{x:$ x is a player that can be dealt card $i\},$ and $C_a=\{i:$ x is a card that can go to player $a\}.$ Also $N_a$ is the number of cards that player $a$ must receive. Here we have $P_1=\{a,b\}=P_2, P_3=\{b,c\}, P_4=\{a,b,c\},$ and $C_a=\{1,2,4\},C_b=\{1,2,3,4\}, C_c=\{3,4\},$ with $N_a=1,N_b=2,N_c=1.$

List the set of allowed player card pairs:

$L=\{(1,a),(2,a),(4,a),(1,b),(2,b),(3,b),(4,b),(3,c),(4,c)\}$

Draw from list $L$ uniformly, say you get $(2,b)$. Give card 2 to player $b.$ Remove all cards of the form $(2,\cdot)$ from the list since we no longer have card 2, to get

$L=\{(1,a),(4,a),(1,b),(3,b),(4,b),(3,c),(4,c)\}$

Since player $b$ was given a card, reduce $N_b$ by 1 to $N_b=1.$ If $N_b$ had become zero, you would have removed all pairs with $b$ in the second coordinate from the list as well since Player $b$ would have got the number of required cards.

Continue with 3 more iterations, since you had 4 cards in total to deal.

The algorithm uniformly chooses pairs from the currently admissible set of pairs, recursively updating admissible sets, by the properties of conditional probability it samples the admissible initial space uniformly.

Answer 2

So, I've been busy with implementing the algorithm of @kodlu. Here is my Python code for anyone walking into a similar problem.

import random


random.seed(0)
### Which card each player can receive
poss = [{1, 2, 4}, {1, 2, 3, 4}, {3, 4}]
N = [1, 2, 1]
num_players = len(poss)  # in my case: 3 players


# The final deal
deal = [set() for _ in range(num_players)]

# The cards that need to be divided
cards = set().union(*poss)
assert len(cards) == sum(N)  # all cards must be divided
# The allowed (card,player) pairs
L = []
for player in range(num_players):
    L += [(card, player) for card in poss[player]]

while True:
    repeat = True
    while repeat:  # we repeat this untill L doesn't change
        repeat = False
        ### e.g. if a player has 3 allowed cards and he needs 3 cards, we can
        # give all cards to that player. This is needed to avoid impossible games.
        unique = {player: 0 for player in range(num_players)}
        unique_card = {player: [] for player in range(num_players)}
        for card, player in L:
            unique[player] += 1
            unique_card[player].append(card)

        # Discard those cards
        for player in range(num_players):
            if unique[player] == N[player] and N[player] != 0:
                cards_to_receive = set(unique_card[player])
                # As all remaining cards for the player are divided he does not
                # need any more cards.
                N[player] = 0
                # Add the cards to the final deal
                deal[player].update(cards_to_receive)
                # We can discard all pairs of the player and all pairs containing
                # a card that has just been given to this player.
                L = [pair for pair in L
                          if (pair[1] != player and
                              pair[0] not in cards_to_receive)
                ]
                cards -= cards_to_receive
                repeat = True

    # If there are no cards left to divide, break
    # (else, randint gives an error)
    if L == []:
        break

    # Draw a random (card,player) pair from L
    rand = random.randint(0, len(L)-1)
    card, player = L[rand]

    # Add the card to the final deal
    deal[player].add(card)
    # Discard this pair and this card
    N[player] -= 1
    if N[player] == 0:
        # Discard this player
        L = [i for i in L if i[1] != player]
    cards.discard(card)
    L = [i for i in L if i[0] != card]

# Check if the answer is correct
if cards != set():
    print('Something went wrong...')
    print(f'Leftover: {cards}')
    print('Maybe try to deal again')

print(deal)

Although this works in most cases, I could find cases for which the program found an impossible situation, a simple fix is trying to deal the cards out again. However, for my use (and the cases my program gives it) it works just fine and I do not need to re-deal the cards.

Still, I did not find more elegant solutions to this problem (where there is no need to re-deal), so help is still very much appreciated.