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

1 次查看（过去 30 天）
Grace
Grace 2014-11-6
评论： Guillaume 2014-11-8
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 个评论
Guillaume
Guillaume 2014-11-6
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 2014-11-8
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].

请先登录，再进行评论。

请先登录，再回答此问题。

回答（3 个）

Thomas Pfau
Thomas Pfau 2014-11-6
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 2014-11-6
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 个评论
Guillaume
Guillaume 2014-11-6
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.

请先登录，再进行评论。

Titus Edelhofer
Titus Edelhofer 2014-11-6
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 个评论
显示 1更早的评论
Grace
Grace 2014-11-6
编辑：Grace 2014-11-8
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Operators and Elementary Operations 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by