Would you mind sharing your proof of this? I don't think you are correct. It seems to me that OP's algorithm is correct and will yield all permutations with equ

Would you mind sharing your proof of this? I don't think you are correct. It seems to me that OP's algorithm is correct and will yield all permutations with equal probability. All he's doing is picking a random card from the sorted deck and moving it to the top of the un-sorted deck. The sorted deck then becomes one card smaller. For N = 2, In position 1 you choose card 1 with 50% and card 2 with 50% probability, and card 2 is just the remaining card. Thus p(12) = 50% p(21) = 50% For N = 3, In position 1 you choose card 1 with p=1/3, card 2 with p=1/3, and card 3 with p=1/3: p(1xx) = 33% = 1/3 p(2xx) = 33% p(3xx) = 33% Then using the remaining 2 cards you just do the N=2 case from before, and so you have: p(123) = 50% x 33% = 1/6 p(132) = 50% x 33% etc