Introduction
In Another Permutation Problem, given a number n, the goal is to maximize an objective function over the set P(n) of all permutations of [1, n]:
max { cost(p), p in P(n) }
where
cost(p) = Sum(i * p(i), 1 <= i <= n) - Max(i * p(i), 1 <= i <= n)
Approaches
Brute force
It took 17 sec to return the solution for n=11.
Since permutation set size is n!, enumerating all the states via backtracking does not scale as n value increases.
But it gives an intuition of the max solution pattern. From the data, the optimal solution for n depends on a 2nd index k, 1 <= k <= n. It has the following shape:
p = [1, 2, ..., k-1, n, n-1, ..., k]
Simplify the problem
To solve the original problem, we break it down into sub-problems that are simpler to solve.
The Max value M of the elements in the Sum / Max functions is fixed:
M = Max(i * p(i), 1 <= i <= n)
We restrict the set of permutations that are candidates for the optimization, from P(n) to P(n, M), to comply with the constraint M.
max { cost(p), p in P(n, M) }
For p in P(n, M), the new cost to maximize is now a linear combination minus a constant
cost(p) = Sum(i * p(i), 1 <= i <= n) - M
Greedy
Greedy approach efficiently computes the maximal solution of the subproblem. It assigns values starting at n down to 1. At each step i, n >= i >= 1, the rule is to assign the highest available value such that i * p(i) <= M.
The subproblem complexity is O(n log(n)). We use an ordered tree as the data structure. For each iterations, we query the DS and assign the returned value to the permutation current index. Finally we remove the allocated value from the DS.
Visualization
There is no need to solve all sub-problems for all values in the range [n, ..., n * n]. The candidates can be found by generating products i * j, 1 <= i <= n, 1 <= j <= n.
Here's the symmetric matrix of all possible product values, for n = 10:
The blue lines are the "reverse" diagonals in the matrix. They are parabolic functions (curved lines), for each index i, 1<= i <= n:
j: (i+1-j) * j
j: (2 - j) * j
j: (3 - j) * j
...
j: (11 - j) * j
The list of unique product values from the matrix is
hence enumerating each subproblems we need to solve.
Operation Research
Finding the right permutation can be considered as an assignment problem: each index i should be assigned to a value j. The assignment should maximize the cost function while respecting the constraints. If i * j > M, remove associated edge in the bipartite graph.
3 important classes of OR problems, from most generic to most specific are
