I would respectfully like to contribute to this very interesting and rich thread which has already been running very long. However, I would like to ask all other contributors I they could possibly give

• a link to where their algorithm has appeared in the literature or can be found in a library,
• a proof, maybe, why the given method is correct in the general case and not just with a few selected examples,
• a few judiciously included comments here and there to explain the meaning of certain variables or some operations.

The subject of permutations seems to be of immensely general interest and the internet is full of articles explaining the concept and giving nice examples in virtually all known programming languages.

Special thanks go to @le_m whose answer not only explicitly mentions the name of Heap's method, but also provides a fine benchmark over all other algorithms proposed in the thread.