This question is a variant of a previous one; it was originally a posed as an edit of this former question, but I came to think it could be more suitable to pose it anew.
Assume I have a deck of cards that I would like to shuffle. Unfortunately, the deck is so big that I cannot hold it entirely in my hands. Let's say that the deck contains M cards, and that the operation I can perform are: 1. cut (deterministically) a deck into any number of sub-decks, without looking at the cards but remembering for all i where the i-th card from top of the original deck has been put; 2. gather several decks into one deck in any order (but assume that we do not intertwin the various decks, nor change the order inside any of them); 3. shuffle any deck of at most n cards. Assume moreover that such a shuffle consist in applying an unknown random permutation drawn uniformly.
Due to arithmetic arguments, it is not possible to achieve uniform distribution over all permutations of the original deck by such shuffles (see David Speyer's answer to the question above). However, one can can consider partial uniformity as follows.
Call a random permutation of $\{1,\ldots,M\}$ $r$-uniform if the law of $((a_1),\ldots,(a_r))$ is uniform for all tuples $(a_1,\ldots,a_r)$ of $\{1,\ldots,M\}$. Then, what is the maximal such $r$ that can be achieved by a process as described above? Given a $r$, how many shuffles are needed to achieve $r$-uniformity?
Note that this measure of uniformity makes sense for the game Race for the galaxy, since some subsets of cards play well together, and one wants to break the artificial weight given when playing a game to the event that such cards are close.
Here is a first thing one can say: if $M=2n$ and $n$ is even, then it is possible to achieve $1$-uniformity in $4$ partial shuffles. Simply cut the deck in two equal sub-decks, shuffle both, gather them, divide the result into a sub-deck containing the first and third quarters and another containing the second and fourth quarters, shuffle both, and gather them. At the end, each individual card has random distribution.
