1
$\begingroup$

We want to distribute 3*n known cards among 3 players evenly given a set of constraints that prohibits some players from having certain suits.

For example: We want to distribute 1H, 2H, 3S, 4S, 5D, 6D (second letter refers to suit of card) among three players A, B, C such that A does not get any card of suit Hearts.

Is there an efficient algorithm that gives a random valid distribution given the constraints?

I have tried successively assigning each player a random card and checking if the constraints are satisfied for that player. If they are not satisfied, we save the chosen card for later and try again with a random card. This does not work in cases when we have only one card left to assign and we are forced to deal that card to a player that cannot have the card of that suit. Trying to satisfy the constraints from this condition by making random swaps with other cards can still not be enough to guarantee all card assignments follow the constraints.

What is the most efficient way to do this?

Edit: Clarifying the constraints

The known cards are a subset of standard deck of cards. Each constraint is in the form of player X cannot have cards of suit Y.

Edit #2: There exists at least one way to distribute cards satisfying all the constraints

$\endgroup$
2
  • $\begingroup$ Is your desired running-time includes time for pre-processing like ordering the cards prior to distribution? Is there any assumption about the set of cards, like can we assume they are the regular deck of cards. Also can you give further details about the constraints. $\endgroup$
    – Russel
    Jan 1, 2023 at 10:51
  • $\begingroup$ Thanks I have edited the post. The known set of cards is a subset of regular deck of cards and each constraint is in the form of player X cannot have cards of suit Y. Regarding the running-time, it does include ordering cards prior to distribution but running-time is not a strict requirement so I have removed it from the post. Any reasonable running time will do. $\endgroup$
    – SAKO
    Jan 1, 2023 at 11:01

1 Answer 1

1
$\begingroup$

Consider $X = [x_1, x_2, …, x_{3n}]$ the sequence of cards. For $i \in \{1, …, 3n\}$, denote $s(i)\subseteq \{A, B, C\}$ the set of players allowed to get card $x_i$. For $i\in \{1, …, 3n\}$ and $a, b, c\in \{1, …, n\}$, denote $f(i, a, b, c)$ the number of possibilities to distribute cards $1, …, i$ among $A$, $B$ and $C$, assuming that they can only receive respectively $a$, $b$ and $c$ cards.

Considering the possibilities to give card $i$, we get: $$f(i, a, b, c) = 𝟙_{A\in s(i)}f(i-1, a-1, b, c) + 𝟙_{B\in s(i)}f(i-1, a, b-1, c) + 𝟙_{C\in s(i)}f(i-1, a, b, c-1)$$ where $𝟙_{A\in s(i)}$ is equal to $1$ if $A\in s(i)$ and $0$ otherwise (and same for $B$ and $C$).

The base cases are:

  • $f(i, a, b, c) = 0$ if $a< 0$ or $b<0$ or $c< 0$;
  • $f(0, 0, 0, 0) = 1$.

This gives the idea of a $\mathcal{O}(n^4)$ (actually $\mathcal{O}(n^3)$ because $a+b+c =i$) dynamic programming algorithm to compute the number of possibilities to distribute all $3n$ cards to $A$, $B$ and $C$: this is $f(3n, n, n, n)$. Since you consider a standard card set, the complexity is not a problem.

Now to create a random distribution, you can use the values previously computed:

  • set $a, b, c = n$
  • for $i =3n$ down to $1$:
    • give card $x_i$ to player $A$ with probability $\dfrac{𝟙_{A\in s(i)}f(i-1, a-1, b, c)}{f(i, a, b, c)}$ and decrease $a$ by one;
    • same thing for other players (those are disjoints events, so that a card can only be given to one player).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.