7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Marzio De Biasi Oct 21 '11 at 6:57
  • 1
    $\begingroup$ 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! :) $\endgroup$ – Gopi Oct 21 '11 at 7:32
  • $\begingroup$ @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... $\endgroup$ – colinfang Oct 21 '11 at 10:28
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Oct 21 '11 at 10:56
  • $\begingroup$ @Vor: looks a lot like what I said? =) $\endgroup$ – Gopi Oct 21 '11 at 12:54
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Shouldn't that be a recurrence in five variables, where the fifth variable is the length of the current run? $\endgroup$ – Peter Taylor Oct 24 '11 at 12:28
  • $\begingroup$ @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. $\endgroup$ – David Eppstein Oct 24 '11 at 14:53
0
$\begingroup$

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 @Gopi 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.

$\endgroup$
  • 2
    $\begingroup$ And the same question here: why does this produce a near-uniform distribution? $\endgroup$ – Jukka Suomela Oct 22 '11 at 13:57
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why does this produce a near-uniform distribution? $\endgroup$ – Jukka Suomela Oct 22 '11 at 13:56
  • $\begingroup$ @JukkaSuomela: it starts with a random stack of cards and reordering is not biased (every card has the same probability of being reordered). $\endgroup$ – nimi Oct 22 '11 at 19:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Shor Oct 22 '11 at 22:37
  • $\begingroup$ @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). $\endgroup$ – nimi Oct 23 '11 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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