I am searching an algorithm which gives me the next permutation with a specific strength.
A permutation of length n is defined with the elements (1,2,3,...n)
What is the strength of a permutation?
The strength of a permutation with length 10 is definded as |a1-a2|+|a2-a3|+...+|a9-a10|+|a10-a1|.
For example:
(1,2,3,4,5,6) has the strength 10
(1,2,6,3,4,5) has the strength 14
Exist there a formula to compute the next permutation of a given strength and length, or its necesary to compute all elements?
Is ranking/unranking of the subsets possible?
The next permutation function should return the next lexicographical permutation within the subset defined by the given strength and length and without compute the intermediate permutations different strengths.
This is a nicely masked problem in combinatorics. First, note that this is a ring of integers; the linear "array" is an implementation choice, rather than part of the strength analysis. Let's look at the second case, given as (1,2,6,3,4,5):
1
5 2
4 6
3
Every element appears in exactly two terms. Thus, we have a simple linear combination of the elements, with coefficients of -2, 0 2. If the element is larger than both neighbors (e.g. 5), the coefficient is 2; if smaller than both neighbors (e.g. 1), it's -2; if between, the two abs operations cancel, and it's 0 (e.g. 4).
Lemma: the strength must be an even number.
Thus, the summation and some transformations can be examined easily enough with simple analysis. The largest number always has a coefficient of +2; the smallest always has a coefficient of -2.
You can find "close relative" permutations by finding interchangeable elements. For instance, you can always interchange the largest two elements (6 and 5) and/or the smallest two elements (1 and 2), without affecting the strength. For instance, 6 and 5 can be interchanged because they're strictly larger than their neighbors:
(6-2) + (6-3) + (5-1) + (5-4) =
(5-2) + (5-3) + (6-1) + (6-4) =
2*6 + 2*5 - 2 - 3 - 1 - 4
1 and 2 can be interchanged, even though they're adjacent, for a similar reason ... except that there are only three terms, one of which involves the pair:
(5-1) + (2-1) + (6-2) =
(5-2) + (2-1) + (6-1) =
5 + 6 - 2*1
Depending on the distribution of the set of numbers, there will likely be more direct ways to construct a ring with a given strength. Since we do not yet have an ordering defined on the permutations, we have no way to determine a "next" one. However, the simple one is to note that rotations and reflections of a given permutation will all have the same strength:
(1,2,6,3,4,5)
(2,6,3,4,5,1)
(6,3,4,5,1,2)
...
(5,4,3,6,2,1)
(4,3,6,2,1,5)
...
Does that get you moving?
Addition w.r.t. OP updates:
There are several trivially strength-invariant swaps available. I've already mentioned the two extreme pairs (6-5) and (1-2). You can also swap adjacent, consecutive numbers: that adds (4-5) and (3-4) in the above example. From simple algebraic properties, you can often identify a 2-element swap or 3-element rotation (respecting an increase in lexicographic position) that generates the next desired permutation. For instance:
(5, 6, 1, 3, 4, 2)
(5, 6, 1, 4, 2, 3) rotate 3, 4, 2
(5, 6, 1, 4, 3, 2) swap 2, 3
However, there are irruptions in the sequence that you'd be hard-pressed to find in this fashion. For instance, making the leap to change the first or second element is not so clean:
(5, 6, 3, 1, 4, 2)
(5, 6, 3, 2, 4, 1) swap 1, 2 -- easy
(6, 1, 2, 4, 5, 3) wholesale rearrangement --
hard to see that this is the next strength=14
I feel that finding these would require a set of algebraic rules that would find the simple moves and eliminate invalid moves (such as generating 563421 before the "wholesale rearrangement" just above). However, following these rules would often take more time than working through all permutations.
I'd love to find that I'm wrong on this last point. :-)
