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.

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.