We present recursive shuffle coding, a general method for optimal compression of unordered objects using bits-back coding. Data structures that can be compressed with our method include multisets, graphs, hypergraphs, and others. Unlike plain shuffle coding, our method allows 'one-shot' compression where only a single such object is to be compressed. We further present incomplete shuffle coding, allowing near-optimal compression of large unordered objects with intractable automorphism groups. When combined, these methods achieve state-of-the-art one-shot compression rates on various large network graphs at competitive speeds. We release an implementation that can be easily adapted to different data types and statistical models.