Did you try this kata in any of the other languages? I am getting timeout errors, and it looks like a ton of people are skipping it. I might have to walk the test suite back a little...

You guys are absolutely right; this solution isn't faster or simpler than an iterative solution.

I've tried rewriting it 7 or 8 times now, and ended up with a version that cuts out the recursion and a lot of the extra string and list allocations.

Yep, I totally agree that it's not the best in terms of performance. At the very least, indeed it can be slightly modified (like laoris' solution) to get rid of unnecessary splits, which removes one extra power of n.

Hey, this is a clever solution, but I don't think you should be doing string concatenation in a loop.

I'd have to do some benchmarks but eyeballing this, it looks like you have O(n⁴) in terms of time complexity.

You are bumping into Joel Spolsky's Shlemiel Anti-pattern: http://www.joelonsoftware.com/articles/fog0000000319.html

I would strongly suggest adding a test case like this:

results = [tuple(p) for p in permutations([1, 2, 2])]

expected_results = [(1, 2, 2), (2, 1, 2), (2, 2, 1)])

Test.assert_equals(sorted(expected_results), sorted(results))

And please review your reference implementation for passing this test case. It doesn't pass, neither do a lot of successful code submissions.

A good permutation generator shouldn't rely on some external code which removes duplicate occurences. In your case it's set, it's highly recommended to use sorted(...) instead of set(...), thus you will see duplicates instead of hiding them

Great, I really love it.