Finding a maximum "score" of a permutation

Question

Consider an array of a permutation P of length n (n > 2), namely some order of the integers 1 through n.

Example of P with length n = 7, [6,5,2,3,7,1,4]

A "score" of a permutation is measured by the amount of indices i (0 <= i <= n-3) that satisfy the condition, P[i] >= P[i+1] + P[i+2].

The score of the example P is 2 at i = 1, 5 (5 >= 2 + 3, 7 >= 1 + 4)

Could we find the maximum score among all possible permutation of length n?

Here are some bruteforce solutions:

n = 3; max = 1 (3 2 1)
n = 4; max = 2 (4 3 1 2)
n = 5; max = 2 (5 4 3 1 2)
n = 6; max = 2 (6 4 2 1 3 5)
n = 7; max = 3 (7 5 1 4 6 3 2)*
n = 8; max = 4 (8 5 3 2 7 6 1 4)
n = 9; max = 4 (9 8 5 3 2 7 6 1 4)
n = 10; max = 5 (10 8 2 6 9 5 4 1 3 7)
n = 11; max = 5 (11 10 8 2 6 9 5 4 1 3 7)
n = 12; max = 6 (12 7 3 4 10 9 1 6 11 8 2 5)
.
n = 15; max (currently) = 8; (15 13 1 11 9 2 7 14 10 4 6 12 8 3 5)
.
n = 20; max (currently) = 10 (20 15 1 10 19 14 2 9 18 13 3 8 17 12 4 7 16 11 5 6)

There seems to be a strategy of placeing digits in this manner:

20 15 1 10
19 14 2 9
18 13 3 8
17 12 4 7 
16 11 5 6

to achieve a 5 blocks of score = 2. But the solution of n = 15 with max = 8 suggests otherwise by joining 2 score 2 blocks

15 13 1 11
 11 9 2 7 | 14 10 4 6 | 12 8 3 5

Could we possibly find a formula or an optimal strategy for this? Thank you!

• Jonas Wilms: „7 5 4 1 6 3 2" - Isn‘t this max=2?
• Jonas Wilms: (but 7 4 3 1 2 (56) would be max=3)
• user31824378: Thank you for pointing out a mistake in my example @JonasWilms!, I have edited the question to include a valid permutation instead.

Answer 1

I adopted a Divide And Conquer strategy which can be described as follows.

Suppose we want to find an optimally scoring permutation of A = {1, ... , n}. Choose usize and vsize so that usize + 2 + vsize = n. Let U be any subset of A of size usize.

Suppose p,q, p != q, are in A and not in U, define S(U,p,q) as the optimal score attainable from permutations of elements of U followed by p then q. Define V = A - U - {p,q} and T(p,q,V) as the optimal score attainable from p, q then permutations of elements of V. Then the maximum score attainable by any permutation of elements of A is

MAX_{U,p,q} S(U,p,q) + T(p,q,V)

My naive O(n!) permutation 'brute force' exhaustive search program gave me (3 7 12 11 1 10 8 2 6 13 9 4 5) and (5 12 11 1 9 13 10 3 7 14 8 6 2 4) for n=13 and 14 scoring 6 and 7 respectively.

My not-production-level-tested exhaustive O(n^2(nCk)k!) for k = floor((n-1)/2) permutation divide and conquer program found examples of optimal sequences for n = 15, to 22 inclusive, (13 11 2 8 7 1 5 14 10 4 6 15 12 3 9), (12 10 2 8 6 1 5 14 15 11 4 7 16 13 3 9), (13 9 4 5 15 8 7 1 6 16 12 2 10 17 14 3 11), (12 10 2 6 13 9 4 5 17 14 3 11 18 16 1 15 7 8), (16 11 5 6 15 12 3 9 8 1 7 18 14 4 10 19 17 2 13), (18 13 5 8 16 9 7 1 6 19 15 4 11 20 17 3 14 12 2 10) , (13 16 12 4 8 17 10 7 2 5 20 19 1 18 14 3 11 21 15 6 9), (17 12 5 7 19 16 3 13 11 1 8 21 15 6 9 22 20 2 18 14 4 10) with scores 8, 8, 9, 9, 10, 11, 11 and 12 respectively.

• Eric Postpischil: Readers should observe these results exceed n/2 for 15 (score 8) and 17 (score 9).
• user31824378: Thank you for your contribution with this strategy and your exhaustive program to achieve an example of a sequence to fill in the gaps in n >=15. Will definitely be looking more into this!

Answer 2

You have indeed identified a pattern that leads to a minoration of the score you have just defined.

We are going to show that the best permutation of N integers achieve at least a score of 2*floor(N/4)-3.

Proof of the statement:

case 1: Take N an integer divisible by 4, such that N=4n

Take these 4 columns of integers and n rows as you have just shown, namely

4n 3n 1 2n
4n-1 3n-1 2 2n-1
4n-2 3n-2 3 2n-2
...
4n-k+1 3n-k+1 k 2n-k+1
...
3n+1 2n+1 n n+1

then all integers are listed and if you build a permutation from here. You are sure to have 2n integers matching your criteria and 2n integers not matching it, because in the first column integers are always greater than the sum of the one in columns 2 and 3 and the same is true for the 2nd column. More explicitly:

Take k in {1, 2, ..., n} then the k-th line is 4n-k+1 3n-k+1 k 2n-k+1 , we can see that 4n-k+1 >= 3n+1 = (3n-k+1) + k and 3n-k+1 >= 2n+1 = (2n-k+1) + k .

Then you know that the permutation that maximizes your score does at least as good as this one. And this one achieves a score of 2n=N/2=2*floor(N/4) such integers.

case 2: N is now a general integer.

You can write it N=4n+k with k equal to 0, 1, 2, 3. The constuction above can be done with at most 3 spare integers leading to a score at least of 2n-3=2*floor(N/4)-3 .

end of proof.

By intuition, i would say that N/2 is the general behaviour of your score and it cannot be much higher.

• ravenspoint: "achieves a score of 2n" n is the total number of integers. The score is the number of indices that meet the criterium. So the score could never be larger than n and certainly not 2n. In the 1st example n is 7 and the score is 2.
• Eric Postpischil: This answer uses N for the number of integers. Its n is N/4, so 2n is N/2. Yes, it is not the same labeling as in the question, but it is not incorrect in that regard.
• ravenspoint: The answer states " such that N=4n"
• Eric Postpischil: Yes, so? It shows 4 columns of n rows, which contain 4n = N integers. Thus, it is working with N integers, and each is a different integer from 1 to N. The columns make it visible that the first number in each column equals or exceeds the sum of the next two, and the second also equals or exceeds the next two after it. Therefore, it shows 2n cases where OP’s criterion is satisfied. When reshaped from a matrix into a single line, it is a permutation of the integers from 1 to N whose score is 2n = N/2.
• Jenetai_pasvu: Thank you for your comment, I have edited my answer to the post to try to make it clearer, still using N to refer to the number of integers permuted by the permutation though.
• ravenspoint: "the best permutation of N integers" The question is about the permutation of n integers. Please do not confuse everyone by changing the definition of symbols in the original question.
• user31824378: Thank you for your detailed proof! I wonder if we could extend this strategy to explain other behaviours of the solution for k=15 and more. Thank you again!