  Random permutations with distribution conditionally uniform given the set of
record values can be generated in a unified way, coherently for all values of
$n$. Our central example is a two-parameter family of random permutations that
are conditionally uniform given the counts of upper and lower records. This
family interpolates between two versions of Ewens' distribution. We discuss
characterisations of the conditionally uniform permutations, their asymptotic
properties, constructions and relations to random partitions.
