Run results for: Classic Permute vs Johnson-Trotter Permute

Run details:

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36 Edg/117.0.2045.47

Browser: Chrome 117

Operating system: Windows

Device Platform: Desktop

Date tested: one year ago

Test name	Executions per second
Classic	31153.1 Ops/sec
Johnson Trotter	285938.6 Ops/sec

Tests:

Classic
function permuteSlice(arr) { function generate(input, output, permutations) { if (input.length === 0) { permutations.push(output.slice()); } for (let i = 0; i < input.length; i++) { let newInput = input.slice(0, i).concat(input.slice(i + 1)); output.push(input[i]); generate(newInput, output, permutations); output.pop(); } return permutations; } return generate(arr, [], []); } permuteSlice([1, 2, 3, 4, 5])
Johnson Trotter
function johnsonTrotterPermute(arr) { const permutations = []; function generate(n, input) { if (n === 1) { permutations.push([...input]); return; } generate(n - 1, input); // Recursively generate permutations for n - 1 for (let i = 0; i < n - 1; i++) { // Decide which two elements to swap based on the parity of n if (n % 2 === 0) { [input[i], input[n - 1]] = [input[n - 1], input[i]]; } else { [input[0], input[n - 1]] = [input[n - 1], input[0]]; } generate(n - 1, input); } } generate(arr.length, arr); return permutations; } johnsonTrotterPermute([1, 2, 3, 4, 5])