This question is mainly a curiosity, but comes from a practical experience (all players of *Race for the galaxy*, for example, must have ask themselves the question).


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 $kn$ cards, and that the operation I can perform are: 1. cut 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.


Here is the question: is it possible to design a finite number of such operations so that the resulting deck has uniform law among all possible permutations of the original deck? If yes, how many shuffles are necessary, or sufficient, to achieve that ?


The case $k=2$ seems already interesting.



How to shuffle a deck by parts?
A truly uniform distribution, no. (Well, your question is not completely well posed, but I will argue this for most ways of making it so.) There are $(kn)!$ factorial ways to shuffle a deck of $kn$ cards. So you want each permutation to occur with probability $1/(kn)!$. In particular, for every prime $p \leq kn$, you want $p$ to occur in the denominator of the probability that each permutation occurs. Let's look at your operations: Reordering $i$ decks can only introduce primes $\leq i$. Perfectly shuffling an $n$ card deck can only introduce primes $\leq n$. Cutting depends on what mathematical model you use for cutting; if all cut points are equally likely, you only get primes dividing $n(n-1)\ldots (n-i+1)$. I imagine other models of cutting will cause similar problems.


The more commonly studied question is how to get a probability distribution that is extremely close to random. There are lots of good results on this; see [Trailing the Dovetail Shuffle to its Lair](https://projecteuclid.org/journals/annals-of-applied-probability/volume-2/issue-2/Trailing-the-Dovetail-Shuffle-to-its-Lair/10.1214/aoap/1177005705.full).


