I just thought of it this way: You're implementing "n P n" which just reduces to n factorial. So you just have to show that your 1st iteration is choosing from

I just thought of it this way: You're implementing "n P n" which just reduces to n factorial. So you just have to show that your 1st iteration is choosing from n items, your 2nd iteration is choosing from (n - 1) items, ... the (n - 1)th iteration is choosing from 2 items. (Choosing from 1 item is a noop, of course.) All we have to do now to see that Fisher-Yates is fair is show that each shuffle can be produced by it. Given a desired shuffle, it is easy to construct the trace that results in it, and we are done. You mean: Given a desired shuffle, you show you can construct the only trace that results in it.