Problem

Given n, generate all permutations from the string of size n that starts with 'a' to char('a' + n)

Solutions

• B.Heap's algorithm
• University of Exeter's algorithm
• Bogomolny's algorithm
• Spreading is just natural backtracking
• Johnson-Trotter's algorithm
• Factorial number system
• Inverse selection sort
• C++ STL's next_permutation function
• Injection is a natural Haskell implementation
• Haskell also has a builtin function to generate permutations
• Someone on Haskell Cafe introduced an algorithm based on selections

Benchmarking

Benchmarking is done for n = 11. Time measured in seconds.

On my desktop

Algorithm	C++	Lua	Haskell
HeapPermute	3	54
Exeter	3	59
Bogomolny	7	60
Spreading	8	63
JohnsonTrotter	9	71
InverseSelect	15	70
Factoradic	21	84
Builtin	7		16
Injection			19
Select			22

On my laptop

Algorithm	C++	Lua	Haskell
HeapPermute	44
Exeter	25
Bogomolny	26
Spreading	29
JohnsonTrotter	26
InverseSelect	42
Factoradic	51
Builtin			44
Injection			46
Select			49

Remarks

• HeapPermute is fastest
• Haskell's performance is better than expected

Todo

• Explain HeapPermute