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

2 views (last 30 days)
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.
  2 Comments
Guillaume
Guillaume on 6 Nov 2014
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
Grace on 8 Nov 2014
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].

Sign in to comment.

Answers (3)

Thomas Pfau
Thomas Pfau on 6 Nov 2014
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.

Guillaume
Guillaume on 6 Nov 2014
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
  1 Comment
Guillaume
Guillaume on 6 Nov 2014
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.

Sign in to comment.


Titus Edelhofer
Titus Edelhofer on 6 Nov 2014
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
  3 Comments
Grace
Grace on 6 Nov 2014
Edited: Grace on 8 Nov 2014
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.

Sign in to comment.

Categories

Find more on Characters and Strings in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!