If I understand correctly, if you want your circuit to be able to generate all permutations, you need at least $\lceil \log_2(n!) \rceil$ probabilistic gates, though I'm not sure how the minimal circuit can be constructed.

If I understand correctly, if you want your circuit to be able to generate all permutations, you need at least $\lceil \log_2(n!) \rceil$ probabilistic gates, though I'm not sure how the minimal circuit can be constructed.

UPDATE:

I think that if you take the Mergesort algorithm and replace all comparisons with random choices with appropriate probabilities you'll get the circuit you are looking for.