How to get a set of numbers with the first and the last absolute difference are the same and etc.

Hi I have n=5, and I will get a set of points for example

a=[ 3 1 4 2 5];

which the elements are from 1 to 5 without replication.

The absolute difference between points in 'a' are shown in 'b',

b=[ 2 3 2 3];

I wish to rearrange the elements in 'a' to get the absolute difference like

c=[ 3 2 2 3];

which the first and the last absolute difference are the same while second and second last absolute difference are the same.

Is it possible to do this? Thanks in advance.

[Guillaume]

You may want to explain why you want to do that and exactly what the constraints are, since as a generic problem it's probably not easy to program.

In particular, with your example you could reorder a to have the [3 2 2 3] difference, but you could also reorder it as [1 2 3 4 5] with a difference of [1 1 1 1] which also fits your criteria of first and last difference being the same and 2nd and 2nd last being the same.

So does the difference need the be maximised, or is it just a reordering of the difference as supplied as input? What should happen if there are more than or less than two identical differences? Is n always 5, or can it go higher?

[Grace]

Hi Guillaume,

My constraint only consider the first and last difference being the same and 2nd and 2nd last being the same. There is no necessary n always equals to 5 but any number that is greater than 4. For example when n=8, we can have [ 4 2 4 7 4 2 4] or [ 3 6 5 3 5 6 3].

Answer 1

[Thomas Pfau]

I wouldn't know how to do this programmatically, but in your example it is possible. You have two pairs of values yielding a difference of 3 (1-4 and 2-5) this leaves 3 as the only number not involved in these pairs thus it automatically has to be placed in the center. Now, there are only two valid pairs with 3 leading to a difference of 2 (1-3 and 3-5). Thus there are 2 options how you could place your values: [4 1 3 5 2] or [2 5 3 1 4].

Programmatically I would assume you would have to check for specific distances between your points and determine whether your order objective is achievable. With 5 numbers this should still be traceable.

Answer 2

[Guillaume]

Assuming n is odd and small enough that perms can be used (<10), and that you want the absolute differences to be strictly decreasing (in the first half):

a = [3 1 4 2 5]; %for example
assert(mod(numel(a), 2) == 1); %numel(a) must be odd
assert(numel(a) < 10); %otherwise perms will take a long time
p = perms(a);  %all permutations of a
pdiff = abs(diff(p, 1, 2)); %absolute difference for each row
ldiff = pdiff(:, 1:end/2); %left half of diff
rdiff = fliplr(pdiff(:, end/2+1:end)); %right half of diff, mirrored
goodrows = find(all(ldiff == rdiff, 2) & all(diff(ldiff, 1, 2) < 0, 2));
gooddiff = pdiff(goodrows, :)
goodperms = p(goodrows, :)

outputs:

gooddiff =

     3     1     1     3
     3     2     2     3
     3     2     2     3
     3     1     1     3

goodperms =

     5     2     3     4     1
     2     5     3     1     4
     4     1     3     5     2
     1     4     3     2     5

[Guillaume]

If you don't care about the ordering of your absolute difference. then just replace the goodrows line with:

goodrows = find(all(ldiff == rdiff, 2));

This will give you all possible combinations of a where differences match. There still may be none.

Answer 3

[Titus Edelhofer]

Hi,

the problem is not generally solvable (without additional flexibility/requirements):

a = [3 5 1 4 2]
a =
   3     5     1     4     2
b = abs(diff(a))
b =
   2     4     3     2

Now there are no "two largest equal"...?

Titus

[Guillaume]

Hence, my comment on the problem:

What should happen if there are more than or less than two identical differences?

[Grace]

Hi,

the absolute differences not necessarily to have ' two largest' equal, what I wish to get is the first absolute difference equal to the last ones, the second equal to the second last ones.

Then from the absolute difference, I can determine the arrangement of 'a'.

Hence, in the example u gave above a=[3 5 1 4 2] with absolute differences [2 4 3 2] did not fulfil the criteria ( 2nd and 2nd last differences are not equal), so the a=[ 3 5 1 4 2] is not the arrangement that I want.

[Guillaume]

Doesn't my answer fulfill your requirements. It'll give you all valid combinations.