Amazon Lab126 Interview Question

Write code to permute a string. I've been programming for 30 years, 20 in games. I have written code to do permutations exactly ... 0 times! It's not all that trivial. I recognized it needed recursion, but I whiffed under the interview pressure. Later looked it up and found he was giving me hints that aren't even in the basic algorithm. I guess I was either unlucky or fortunate (I wasn't at all convinced yet I'd want to work there).