Example of a factorial time algorithm O( n! )

List all permutations of an array is O(n!). Below is a recursive implementation using the swap method. The recursion is inside the for loop and the elements in the array are swapped in position until no more elements remain. As you can see from the result count, the number of elements in the array is n!. Each permutation is an operation and there are n! operations.

def permutation(array, start, result)
    if (start == array.length) then
        result << array.dup  
    end
    for i in start..array.length-1 do
        array[start], array[i] = array[i], array[start]
        permutation(array, start+1,result)
        array[start], array[i] = array[i], array[start]
    end 
    result   
end        


p permutation([1,2,3], 0, []).count  #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!

Traveling Salesman has a naive solution that's O(n!), but it has a dynamic programming solution that's O(n^2 * 2^n)

Generate all the permutations of a list

You have n! lists, so you cannot achieve better efficiency than O(n!).