0

Given a circular array, rearrange the array so that the maximum absolute difference between adjacent elements among all elements is minimum. Can anyone help me with this?

leader
  • 3
  • I don't think TSP works here. Consider a normal array. sorting it will give such and array. Now try to think of a circular array. – WannaBeCoder Nov 01 '14 at 06:35
  • Yeah! I had thought of this way first and I could figure out that it is not giving the correct answer in this way. – leader Nov 02 '14 at 16:38

1 Answers1

0

Sounds like that's equivalent to the travelling salesman problem.

https://en.wikipedia.org/wiki/Travelling_salesman_problem

In your case, each element in the array is a city, and the distance between two cities is the difference between each element.

Here's a paper on a fast solution to TSP that I pulled off arxiv:

http://arxiv.org/ftp/cs/papers/0702/0702133.pdf

Here's a fast TSP solving library:

http://cran.r-project.org/web/packages/TSP/index.html

Your edit makes it no longer related to TSP.

Zaaier
  • 203
  • Yeah! You are right...Can we solve it efficiently for 1000 array elements? If so, can you give the solution? – leader Nov 01 '14 at 06:03
  • @leader (How was that username not already taken?!) I'm not sure. That depends on what you mean by "efficient". I would guess that 1000 elements wouldn't run on your laptop in under a day. That's just a guess. There are also approximate solutions to TSP available. I've never used any of them myself. I don't know how much faster they run. – Zaaier Nov 01 '14 at 06:06
  • @ Zaaier LOL! I took the username a year ago...Thanks! anyway. – leader Nov 01 '14 at 06:13