0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – WannaBeCoder Nov 1 '14 at 6:35
  • $\begingroup$ Yeah! I had thought of this way first and I could figure out that it is not giving the correct answer in this way. $\endgroup$ – leader Nov 2 '14 at 16:38
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah! You are right...Can we solve it efficiently for 1000 array elements? If so, can you give the solution? $\endgroup$ – leader Nov 1 '14 at 6:03
  • $\begingroup$ @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. $\endgroup$ – Zaaier Nov 1 '14 at 6:06
  • $\begingroup$ @ Zaaier LOL! I took the username a year ago...Thanks! anyway. $\endgroup$ – leader Nov 1 '14 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.