arXiv:2611.01028v2 Announce Type: replace Abstract: Sampling a uniformly random permutation of $[n]$ in parallel is a coordination problem: $n$ processors, one per coordinate, must output distinct values. A single round requires a shared seed of $\log n!$ nats, while $n$ rounds require no shared randomness. We determine the tradeoff in between for $R$ rounds, in which the values of each round are written independently given the shared randomness and the earlier output, and the output must be a uniform permutation, exactly or within total-variation error $\varepsilon$. Shared randomness is measured by its support size or by its entropy, and it is either fixed in advance or drawn adaptively during the execution. For exact sampling, all four costs equal one explicit combinatorial quantity up to an absolute additive constant. A fixed error $0<\varepsilon<1$ shortens the seed by $O(1)$ nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is $(1-3\varepsilon/2)\,n!$ up to an additive two for $\varepsilon\le1/2$. The saving is $\Theta((\log n)^2)$ nats in two rounds, with a sharp constant, and of lower order for $R=o(n)$; for $R\sim\rho n$ with $0<\rho<1$ it is linear in $n$, with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only $o(n)$ nats, and at every positive error below it, shared randomness drawn adaptively has strictly smaller entropy than a seed fixed in advance. A central tool is a change of measure that turns lower bounds with error into entropy bounds for a single batch of distinct, nearly independent values. The results for sublinearly and linearly many rounds extend to sampling without replacement.