Example of a factorial time algorithm O( n! )

Question

I'm studying time complexity in school and our main focus seems to be on polynomial time O(n^c) algorithms and quasi-linear time O(nlog(n)) algorithms with the occasional exponential time O(c^n) algorithm as an example of run-time perspective. However, dealing with larger time complexities was never covered.

I would like to see an example problem with an algorithmic solution that runs in factorial time O(n!). The algorithm may be a naive approach to solve a problem but cannot be artificially bloated to run in factorial time.

Extra street-cred if the factorial time algorithm is the best known algorithm to solve the problem.

Answer 1

Generate all the permutations of a list

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

Answer 2

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