# Minimize function on permutations

Problem:

Consider $$[k] = \{ 1, 2, \dots, k \}$$ and function (of two arguments) $$f: [k]^{2} \rightarrow \mathbb{N}$$ that is defined for all $$(n, m) \in [k]^{2}$$ (all ordered pairs of numbers from $$[k]$$). Also, we know that for all $$n, m \in [k]$$ $$f(n, m) = f(m, n) .$$

Also, consider the set $$S_{k}$$ of all permutations on $$[k]$$ and function $$g: S_{k} \rightarrow \mathbb{N}$$ defined as follows $$\sigma = \sigma_{1} \sigma_{2} \dots \sigma_{k} \quad \Rightarrow \quad g(\sigma) = \sum_{i = 1}^{k - 1} f(\sigma_{i}, \sigma_{i + 1}) .$$

The problem is to find at least one permutation $$\sigma \in S_{k}$$ such that $$g(\sigma)$$ is minimal.

Question:

How can we find the desired permutation faster than brute force?

• A knight's tour is a very special permutation.... I'd try backtracking. It is very unlikely that there is a "nice" algorithm. There isn't for the plain knight tour, for one. – vonbrand Mar 4 '20 at 0:24

Hamiltonian path is a special case of your problem. Given a graph $$G$$, let $$f(n,m) = 1$$ if the edge $$(n,m)$$ exists, and $$f(n,m) = 2$$ otherwise. The minimum value of $$g(\sigma)$$ equals 1 iff $$G$$ contains a Hamiltonian path.