<p>One way of doing this is to, at each step, draw a random card from all the remaining decks that satisfy the constraints. I would suggest doing this by shuffling all the decks, and then taking the top card from one of the legal decks, picking a deck with probability proportional to the number of cards left in it.</p>

<p>This has the advantages that (a) in the case of no restriction, it is essentially Fisher-Yates-Knuth shuffling, and so gives a completely uniform permutation, and (b) since it favors decks with more cards, it leaves you with a reasonable chance of not ending with a bunch of cards in just one deck.</p>

<p>I suspect this is a reasonably good algorithm to use in practice, depending on what you want it for. However, it is not equivalent to the process of picking a uniform shuffle that satisfies the constraints, as I argue below. </p>

<p>Suppose you just have two decks, and you have $n/2$ cards in each deck for some large $n$. This question is equivalent to choosing a random way of tiling a length $n$ strip with alternating black or white tiles of length either $1$ or $2$, with the constraint that you have an equal area of black and white. We'll forget both the factor of two that comes from the fact that you can start with either a black or a white tile, and the restriction of equal areas of black and white, since for large $n$ these will contribute lower-order terms. The number of ways of tiling this strip is the $n$<sup>th</sup> Fibonacci number $F_n$, and the ratio of tiles of length $1$ to those of length $2$ is the golden ratio $\phi=\frac{\sqrt{5}+1}{2}$. You can see this because the last tile is either of length $1$ or length $2$, and for a length $1$ tile, there are $F_{n-1}$ ways of tiling the remaining strip, while for a length $2$ tile, there are $F_{n-2}$ ways. The ratio of the two lengths for the tile ending at position $n$ is thus $F_{n-1}/F_{n-2}$, which converges to $\phi$.</p>

<p>The process I sketched above, of choosing a random card from a legal deck, gives $1$ for this ratio of the number of runs of length $1$ do those of length $2$&mdash;a white card will be followed with equal probability by a white one (making a run of length $2$) or a black one (making a run of length $1$). Thus, it doesn't yield a uniform distribution among shuffles.</p>

<p>ADDED :</p>

<p>Here's an idea that will probably come pretty close to a uniform distribution over all allowed shuffles, although I can't analyze it. Suppose you just have two decks. Start by shuffling each deck. Choose a deck, say A, randomly to start the procedure. Take one card from deck A with probability $1/\phi$ and two cards from deck A with probability $1/\phi^2$. Then do the same for deck B. Keep this up, but adjust the probabilities so that the probability of one card from a deck is $1/\phi \pm \epsilon$, where $\epsilon$ is chosen so that you expect to exhaust the two decks at the same time. For more than two decks, or a restriction to no more than $k$ cards from each deck, you can use the same strategy, but you will have to figure out what the appropriate probabilities for choosing each allowed number of cards in the uniform distribution over allowed shuffles.</p>

CC BY-SA 3.0
2011-10-21T22:23:44.800Z
2011-10-22T22:58:16.467Z
2011-10-22T22:58:16.467Z
Peter Shor 
<p>Filter first — find sequences of $4\times 52$ symbols from the alphabet $abcd$ with 52 copies of each letter and no four consecutive copies of the same letter — then randomly shuffle each deck and use your preselected filter to select the order to interleave the decks.</p>

<p>It's not hard to set up a recurrence in four variables for the number of valid sequences with $x_a$ $a$'s, $x_b$ $b$'s, etc. Once you've done that you can build your sequence of $abcd$ letters one letter at a time — once you've picked some letters, the next letter should be chosen with probability proportional to the number of valid sequences of the remaining letters that start with that letter. In this way, you'll get exactly a uniform distribution on all permutations. But this approach takes something like $52^4$ time to compute the recurrence values; probably it's possible to do some combinatorics and find a way to simplify this part of the computation.</p>

CC BY-SA 3.0
2011-10-24T12:28:33.757Z
Shouldn't that be a recurrence in five variables, where the fifth variable is the length of the current run?
Peter Taylor
CC BY-SA 3.0
2011-10-24T14:53:33.467Z
@Peter: I was thinking more in terms of having multiple functions F1, F2, etc., all recurring together, where Fi is the function that encodes the number of sequences that can be concatenated after a run of i, and where they are all recurring together. There are only finitely many different values for the length of the run so it doesn't really count as a variable in the sense that it doesn't contribute more than a constant factor to the complexity.
David Eppstein
CC BY-SA 3.0
2011-10-23T07:42:29.603Z
2011-10-23T07:42:29.603Z
David Eppstein
<p>Similar to the comments on your post, why don't you shuffle the four decks then randomly pick which deck you get each card from?</p>

<p>If you want to prevent 4 consecutive cards from the same pack, intervene in the deck selection if you have 3 already from the same deck (as @Gopi states)</p>

<p>If you wanted to switch to a 'no two consecutive cards from the same deck', then simply remove the deck that you last pop'd from the deck selection.</p>

CC BY-SA 3.0
2011-10-22T13:57:17.543Z
And the same question here: why does this produce a near-uniform distribution?
Jukka Suomela
CC BY-SA 3.0
2011-10-21T15:41:03.777Z
2011-10-21T15:41:03.777Z
tonycoupland
<p>Shuffle all 4 decks into a single stack (keep record from which deck a card comes). Start from top and check your constraints until you find a card that breaks them. Try to insert that card at the top position, then second and so on up to the original position until you find a proper place for it. If there's no such position, put the card at the end of the stack. Repeat with next card.</p>

<p>Remark: If a card at position <em>p</em> breaks the constraints and cannot be placed at any position 1 ... <em>p</em>, it's put at the end of the stack. If it's later re-checked, it either fits</p>

<ul>
<li>at the new position <em>p'</em></li>
<li>at a postion 1 .. <em>p</em>, if other cards have been inserted in the meantime</li>
<li>at a position <em>p</em> ... <em>p'</em></li>
<li>or will be put at the end of the stack again</li>
</ul>

<p>I've no proof that this algorithm terminates (it depends on the exact restrictions), but for "no four (two) consecutive cards from the same deck" it should, as you cannot arrange 4 decks minus one card in such a way that the final card cannot be placed at any position. </p>

<p>EDIT: this algorithm has turned out to be wrong, see discussion below.   </p>

CC BY-SA 3.0
2011-10-22T13:56:27.077Z
Why does this produce a near-uniform distribution?
Jukka Suomela
CC BY-SA 3.0
2011-10-22T19:11:01.740Z
@JukkaSuomela: it starts with a random stack of cards and reordering is not biased (every card has the same probability of being reordered).
nimi
CC BY-SA 3.0
2011-10-22T22:37:41.733Z
Suppose you have two decks, and have the constraint: no runs of length 4 from the same deck. In the lower half of the deck, 1/2 of the runs from the same deck will be of length 1, 1/4 of length 2, and 1/4 of length 3, since your process converts any run of length longer than 3 to a run of length 3, and your reinsertion process will almost surely not reach very deep in your deck. I have no idea what run lengths look like at the top of the deck, but I suspect they're different. This is *not* what you get from a uniform distribution over all allowed shuffles.
Peter Shor 
CC BY-SA 3.0
2011-10-23T08:26:38.997Z
@PeterShor: Ah, now I see. Yes, you're right my algorithm won't lead to a uniform distribution. Thanks for pointing out. In the lower part ever row >= 3 consecutive cards will result in a row of 3. In the upper part a row of 3 can only appear if a row >= 6 is broken up in the lower part. You get only a near uniform distribution if the upper part is very small, i.e. the constraints are rarely broken (or maybe if you start inserting from the current position _p_ backwards to top, but I have to rethink that before making wrong claims again).
nimi
CC BY-SA 3.0
2011-10-22T10:53:31.290Z
2011-10-23T08:29:41.100Z
2011-10-23T08:29:41.100Z
nimi
<p>I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied.</p>

<p>For example, i would like to shuffle 4 decks of cards, and make sure:</p>

<p>Any consecutive 4 cards won't come from the same deck.</p>

<p>Surely I can do the fisher-yates-Knuth shuffling first and then filter out bad permutations, but if the restrictions are strong (e.g. any consecutive 2 cards won't come from the same deck), there will be too many failures.</p>

<p>If i don't mind that if it is slightly unbiased, (of course the less bias the better), how should I do?</p>

CC BY-SA 3.0
2011-10-21T06:57:39.463Z
What do you mean with "consecutive 2 cards"? Two cards with  increasing value (suit doesn't matter)? Two cards with the same suit and increasing value?
Marzio De Biasi
CC BY-SA 3.0
2011-10-21T07:32:53.070Z
Keep 4 stacks, shuffle them. Randomly chose the first card from one of the stack, do the same for the second and third. If they all come from the same stack, then randomly chose the 4th card among the 3 remaining deck. Start again from this 4th card. If at the end your choices are only cards from the same deck, try again! :)
Gopi
CC BY-SA 3.0
2011-10-21T10:28:17.953Z
@Vor: consecutive in the sense of cards in order. e.g  after shuffling u get K,1,8,Q 7 ... i want K18Q not from same deck, 18Q7 not same deck...
colinfang
CC BY-SA 3.0
2011-10-21T10:56:58.537Z
@colinfang: ok. A trivial solution is: shuffle the 4 stacks and merge them picking one card from the top of each stack (s1,s2,s3,s4,s1,s2,s3,s4,...). Another solution is: shuffle the 4 stacks, the repeatedly choose a stack randomly and pick its top card, if the last 3 picked cards come from the same stack then choose the next from the other three stacks.
Marzio De Biasi
CC BY-SA 3.0
2011-10-21T12:54:43.800Z
@Vor: looks a lot like what I said? =)
Gopi
CC BY-SA 3.0
2011-10-21T13:19:18.137Z
@Vor and Gopi: You can improve this procedure by choosing a deck at each step with probability proportional to the number of cards in that deck. This will make the probability distribution closer to uniform, and greatly reduce the probability you're stuck with a bunch of cards from the same deck at the end. It still isn't exactly uniform, as I pointed out in a comment on a now-deleted answer, but it probably comes fairly close.
Peter Shor 
CC BY-SA 3.0
2011-10-21T13:52:38.050Z
@Gopi: ops you're right ... :-) Peter: I also thought about it but didn't have time for a full answer.
Marzio De Biasi
CC BY-SA 3.0
2011-10-21T14:01:10.903Z
@Peter: perhaps a perfect uniform distribution is obtained simply reinserting the stuck cards: for every stuck card insert it at random in the global deck, choosing only among allowed positions for that card. So the algorithm is: join the 4 stacks, shuffle the global stack, scan it and remove invalid cards, at the end reinsert the invalid cards one at a time choosing randomly among valid positions for it.
Marzio De Biasi
CC BY-SA 3.0
2011-10-21T14:15:36.507Z
Who's up for the maths :)?
Gopi
CC BY-SA 3.0
2011-10-21T15:20:10.480Z
@Vor: that won't work. Consider one deck, A, with three cards, and another, B, with two cards, and the constaint that you cannot have three cards in a row. With the algorithm, you get all valid positions equally often from the original shuffle. There's never more than one invalid card, and you'll never get the order ABABA from removing and reinserting the invalid card, so this order is less likely.
Peter Shor 
CC BY-SA 3.0
2011-10-21T16:30:41.350Z
@Peter: in my previous comment the "remove invalid cards" means "remove all the cards which forms the invalid sequence" (in your example remove all 3 cards from A if they appear together in the "global" stack). Furthermore head and tail can be valid positions for the final reinsertions. But perhaps your note is still valid ... I'll think of it.
Marzio De Biasi
CC BY-SA 3.0
2011-10-23T07:55:35.057Z
The combinatorics to weight selecting from different decks is the hard part. Basically the problem of getting a uniform distribution reduces to: given that the cards selected already end with a run of $k$ cards from deck $i$ and the maximum run of cards from a deck permitted is $r$, and given the sizes of the unselected cards from each deck $|C_j|$, count for each $j$ the number of legal sequences of deck selections starting with $j$ which satisfy the run limits. It can be done recursively, but unless there's a nice closed form it won't be efficient.
Peter Taylor
CC BY-SA 3.0
2011-10-23T15:21:21.823Z
@Peter Taylor: you should be able to use information theory techniques to approximate this quite well.
Peter Shor 
<ds.algorithms><randomized-algorithms><permutations>
How to shuffle cards with restrictions?
colinfang
# How to shuffle cards with restrictions?

(Asked by: username_0 on 2011-10-21)

I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied.

For example, i would like to shuffle 4 decks of cards, and make sure:

Any consecutive 4 cards won't come from the same deck.

Surely I can do the fisher-yates-Knuth shuffling first and then filter out bad permutations, but if the restrictions are strong (e.g. any consecutive 2 cards won't come from the same deck), there will be too many failures.

If i don't mind that if it is slightly unbiased, (of course the less bias the better), how should I do?

**Tags:** ds.algorithms, randomized-algorithms, permutations

> **Comments:**
> **username_1**: What do you mean with "consecutive 2 cards"? Two cards with  increasing value (suit doesn't matter)? Two cards with the same suit and increasing value?  
> **username_2**: Keep 4 stacks, shuffle them. Randomly chose the first card from one of the stack, do the same for the second and third. If they all come from the same stack, then randomly chose the 4th card among the 3 remaining deck. Start again from this 4th card. If at the end your choices are only cards from the same deck, try again! :)  
> **username_0**: @Vor: consecutive in the sense of cards in order. e.g  after shuffling u get K,1,8,Q 7 ... i want K18Q not from same deck, 18Q7 not same deck...  
> **username_1**: @username_0: ok. A trivial solution is: shuffle the 4 stacks and merge them picking one card from the top of each stack (s1,s2,s3,s4,s1,s2,s3,s4,...). Another solution is: shuffle the 4 stacks, the repeatedly choose a stack randomly and pick its top card, if the last 3 picked cards come from the same stack then choose the next from the other three stacks.  
> **username_2**: @Vor: looks a lot like what I said? =)  
> **username_3**: @Vor and username_2: You can improve this procedure by choosing a deck at each step with probability proportional to the number of cards in that deck. This will make the probability distribution closer to uniform, and greatly reduce the probability you're stuck with a bunch of cards from the same deck at the end. It still isn't exactly uniform, as I pointed out in a comment on a now-deleted answer, but it probably comes fairly close.  
> **username_1**: @username_2: ops you're right ... :-) Peter: I also thought about it but didn't have time for a full answer.  
> **username_1**: @Peter: perhaps a perfect uniform distribution is obtained simply reinserting the stuck cards: for every stuck card insert it at random in the global deck, choosing only among allowed positions for that card. So the algorithm is: join the 4 stacks, shuffle the global stack, scan it and remove invalid cards, at the end reinsert the invalid cards one at a time choosing randomly among valid positions for it.  
> **username_2**: Who's up for the maths :)?  
> **username_3**: @Vor: that won't work. Consider one deck, A, with three cards, and another, B, with two cards, and the constaint that you cannot have three cards in a row. With the algorithm, you get all valid positions equally often from the original shuffle. There's never more than one invalid card, and you'll never get the order ABABA from removing and reinserting the invalid card, so this order is less likely.  
> **username_1**: @Peter: in my previous comment the "remove invalid cards" means "remove all the cards which forms the invalid sequence" (in your example remove all 3 cards from A if they appear together in the "global" stack). Furthermore head and tail can be valid positions for the final reinsertions. But perhaps your note is still valid ... I'll think of it.  
> **username_4**: The combinatorics to weight selecting from different decks is the hard part. Basically the problem of getting a uniform distribution reduces to: given that the cards selected already end with a run of $k$ cards from deck $i$ and the maximum run of cards from a deck permitted is $r$, and given the sizes of the unselected cards from each deck $|C_j|$, count for each $j$ the number of legal sequences of deck selections starting with $j$ which satisfy the run limits. It can be done recursively, but unless there's a nice closed form it won't be efficient.  
> **username_3**: @username_4: you should be able to use information theory techniques to approximate this quite well.  

---

## 4 answers

### Answer by username_3 on 2011-10-21. Score: 8

One way of doing this is to, at each step, draw a random card from all the remaining decks that satisfy the constraints. I would suggest doing this by shuffling all the decks, and then taking the top card from one of the legal decks, picking a deck with probability proportional to the number of cards left in it.

This has the advantages that (a) in the case of no restriction, it is essentially Fisher-Yates-Knuth shuffling, and so gives a completely uniform permutation, and (b) since it favors decks with more cards, it leaves you with a reasonable chance of not ending with a bunch of cards in just one deck.

I suspect this is a reasonably good algorithm to use in practice, depending on what you want it for. However, it is not equivalent to the process of picking a uniform shuffle that satisfies the constraints, as I argue below.

Suppose you just have two decks, and you have $n/2$ cards in each deck for some large $n$. This question is equivalent to choosing a random way of tiling a length $n$ strip with alternating black or white tiles of length either $1$ or $2$, with the constraint that you have an equal area of black and white. We'll forget both the factor of two that comes from the fact that you can start with either a black or a white tile, and the restriction of equal areas of black and white, since for large $n$ these will contribute lower-order terms. The number of ways of tiling this strip is the $n$th Fibonacci number $F\_n$, and the ratio of tiles of length $1$ to those of length $2$ is the golden ratio $\phi=\frac{\sqrt{5}+1}{2}$. You can see this because the last tile is either of length $1$ or length $2$, and for a length $1$ tile, there are $F\_{n-1}$ ways of tiling the remaining strip, while for a length $2$ tile, there are $F\_{n-2}$ ways. The ratio of the two lengths for the tile ending at position $n$ is thus $F\_{n-1}/F\_{n-2}$, which converges to $\phi$.

The process I sketched above, of choosing a random card from a legal deck, gives $1$ for this ratio of the number of runs of length $1$ do those of length $2$—a white card will be followed with equal probability by a white one (making a run of length $2$) or a black one (making a run of length $1$). Thus, it doesn't yield a uniform distribution among shuffles.

ADDED :

Here's an idea that will probably come pretty close to a uniform distribution over all allowed shuffles, although I can't analyze it. Suppose you just have two decks. Start by shuffling each deck. Choose a deck, say A, randomly to start the procedure. Take one card from deck A with probability $1/\phi$ and two cards from deck A with probability $1/\phi^2$. Then do the same for deck B. Keep this up, but adjust the probabilities so that the probability of one card from a deck is $1/\phi \pm \epsilon$, where $\epsilon$ is chosen so that you expect to exhaust the two decks at the same time. For more than two decks, or a restriction to no more than $k$ cards from each deck, you can use the same strategy, but you will have to figure out what the appropriate probabilities for choosing each allowed number of cards in the uniform distribution over allowed shuffles.


---

### Answer by username_5 on 2011-10-23. Score: 5

Filter first — find sequences of $4\times 52$ symbols from the alphabet $abcd$ with 52 copies of each letter and no four consecutive copies of the same letter — then randomly shuffle each deck and use your preselected filter to select the order to interleave the decks.

It's not hard to set up a recurrence in four variables for the number of valid sequences with $x\_a$ $a$'s, $x\_b$ $b$'s, etc. Once you've done that you can build your sequence of $abcd$ letters one letter at a time — once you've picked some letters, the next letter should be chosen with probability proportional to the number of valid sequences of the remaining letters that start with that letter. In this way, you'll get exactly a uniform distribution on all permutations. But this approach takes something like $52^4$ time to compute the recurrence values; probably it's possible to do some combinatorics and find a way to simplify this part of the computation.

> **Comments:**
> **username_4**: Shouldn't that be a recurrence in five variables, where the fifth variable is the length of the current run?  
> **username_5**: @Peter: I was thinking more in terms of having multiple functions F1, F2, etc., all recurring together, where Fi is the function that encodes the number of sequences that can be concatenated after a run of i, and where they are all recurring together. There are only finitely many different values for the length of the run so it doesn't really count as a variable in the sense that it doesn't contribute more than a constant factor to the complexity.  

---

### Answer by username_6 on 2011-10-21. Score: 0

Similar to the comments on your post, why don't you shuffle the four decks then randomly pick which deck you get each card from?

If you want to prevent 4 consecutive cards from the same pack, intervene in the deck selection if you have 3 already from the same deck (as @username_2 states)

If you wanted to switch to a 'no two consecutive cards from the same deck', then simply remove the deck that you last pop'd from the deck selection.

> **Comments:**
> **username_7**: And the same question here: why does this produce a near-uniform distribution?  

---

### Answer by username_8 on 2011-10-22. Score: 0

Shuffle all 4 decks into a single stack (keep record from which deck a card comes). Start from top and check your constraints until you find a card that breaks them. Try to insert that card at the top position, then second and so on up to the original position until you find a proper place for it. If there's no such position, put the card at the end of the stack. Repeat with next card.

Remark: If a card at position *p* breaks the constraints and cannot be placed at any position 1 ... *p*, it's put at the end of the stack. If it's later re-checked, it either fits

* at the new position *p'*
* at a postion 1 .. *p*, if other cards have been inserted in the meantime
* at a position *p* ... *p'*
* or will be put at the end of the stack again

I've no proof that this algorithm terminates (it depends on the exact restrictions), but for "no four (two) consecutive cards from the same deck" it should, as you cannot arrange 4 decks minus one card in such a way that the final card cannot be placed at any position.

EDIT: this algorithm has turned out to be wrong, see discussion below.

> **Comments:**
> **username_7**: Why does this produce a near-uniform distribution?  
> **username_8**: @JukkaSuomela: it starts with a random stack of cards and reordering is not biased (every card has the same probability of being reordered).  
> **username_3**: Suppose you have two decks, and have the constraint: no runs of length 4 from the same deck. In the lower half of the deck, 1/2 of the runs from the same deck will be of length 1, 1/4 of length 2, and 1/4 of length 3, since your process converts any run of length longer than 3 to a run of length 3, and your reinsertion process will almost surely not reach very deep in your deck. I have no idea what run lengths look like at the top of the deck, but I suspect they're different. This is *not* what you get from a uniform distribution over all allowed shuffles.  
> **username_8**: @PeterShor: Ah, now I see. Yes, you're right my algorithm won't lead to a uniform distribution. Thanks for pointing out. In the lower part ever row >= 3 consecutive cards will result in a row of 3. In the upper part a row of 3 can only appear if a row >= 6 is broken up in the lower part. You get only a near uniform distribution if the upper part is very small, i.e. the constraints are rarely broken (or maybe if you start inserting from the current position _p_ backwards to top, but I have to rethink that before making wrong claims again).  

---

