1

I've got a list of unique integers, and I want to sort them so that the next integer is always as far from all the rest, an it's possible.

For example, {1,2,3,4,5,6,7,8,9} => {1,9,6,2,8,3,7,4,5}

And I need to do it really fast.

Currently, I'm doing it like this:

 static double GetDistanceIndex(int value, List<int> others) { double result=0; foreach (var other in others) { result += Math.Sqrt(Math.Abs(other - value)); } return result; } static List<int> Sort(List<int> items, int initialValue) { items = items.ToList(); List<int> result=new List<int>(); lock (rnd) { while (true) { result.Add(initialValue); items.Remove(initialValue); if (items.Count == 0) { break; } Dictionary<double, List<int>> distances = new Dictionary<double, List<int>>(); foreach (var item in items) { var d = GetDistanceIndex(item, result); if (!distances.ContainsKey(d)) { distances[d] = new List<int>(); } distances[d].Add(item); } var max = distances.Keys.Max(); var l = distances[max]; //if (l.Count == 1) //{ // initialValue = l[0]; //} //else //{ initialValue = l[rnd.Next(l.Count)]; //} } } return result; }

But the problem is, that implemented like this, the algorithm will work extremely slowly for large arrays.

Can anyone suggest to me a better way to do it?

UPDATE

Here's a better description what was done:

{1,2,3,4,5,6,7,8,9}=>

  1. initial seed : 1. Really, it can be any number. We can select 5, and get something like {5,9,1,2,8,3,7,6,4}
  2. From the provided array, 9 is the farthest away from 1 by distances
  3. Because in the list all the numbers are equidistant from 1 and from 9, we can select any of them. I used rand to select 6.
  4. Now we are looking for a number farthest away from {1,9,6}. 2 is selected because abs(2-1)+abs(2-9)+abs(2-6)=12 and is greater than abs(3-1)+abs(3-9)+abs(3-6)=11 or abs(4-1)+abs(4-9)+abs(4-6)=10 or abs(8-1)+abs(8-9)+abs(8-6)=10 or abs(7-1)+abs(7-9)+abs(7-6)=9 or abs(5-1)+abs(5-9)+abs(5-6)=9
  5. etc

UPDATE 1

I'm using this algorithm to select numbers as different from each other as possible from a fixed number of alternatives

UPDATE 2

Dukeling in his answer pointed out to me, that {1,9,2,8,3,7,4,6,5} also conforms to my requirements. This was true, and it's my mistake. I want the numbers to be as far spaced as possible, and 3d number being very close to the first one is not what I intended. So I'm updating the distance function to reflect this

Improve this question
13
  • 2
    Please clarify what do you mean be "far from the rest"? Do you want the sum of absolute values of differences between the adjacent values to be maximum? Commented Oct 6, 2013 at 11:57
  • 2
    Your description of how you want to sort and your example aren’t clear. Commented Oct 6, 2013 at 12:01
  • 1
    By reading GetDistanceIndex, you can see that he actually picks the number for which the sum of the distances to each of the already sorted numbers is maximum. Commented Oct 6, 2013 at 12:11
  • 1
    Is there a point to all this? It seems like an odd "exercise". Commented Oct 6, 2013 at 12:12
  • 1
    CBroe as far as I understand its any number x not yet added to the resulting set s that maximizes Sum[d(x, s[i])] where the distance function d(x,y) is abs(x-y). Commented Oct 6, 2013 at 12:13

2 Answers 2

Reset to default
1

[Edited to conform to new distance function]

You are making unnecessary work by calling GetDistanceIndex() repeatedly. Notice that you don't need to sum everything from scratch everytime. If you have an array like this:

[a, b, c, d, ............, x]

Where a, b, c, and d are already sorted, then, when you insert a new element 'e', the sum of the distance function of any position 'x' in the unsorted set to all the other numbers in the sorted set is only increased by sqrt(abs(x-e)). You don't have to recompute the whole sum from scratch.

So here's how you can optimize it: use some kind of method to store a pair (number, distance). If you were using C, you could, for example, make an array of a structure with two integers, the value itself, and the distance to the sorted set. At each step, you go through every pair (number, distance) that is not in the sorted set and you update its distance attribute. You can keep track of the maximum at the same time. Some pseudo-code:

  • Create an auxiliary buffer S, to hold pairs of (number, distance);

  • Insert every number x different from initialValue in S, with distance = sqrt(abs(initialValue - x)). Keep track of the maximum, m, at the same time;

  • In each step, pick m and move it to the sorted piece of the array. Remove it from S. Then, go to every element y in S and add sqrt(abs(y.number-m.number)) to y's distance. Again, you need to keep track of the maximum as you do this. Keep repeating that until every element is sorted.

It's not a brilliant solution; it runs in O(n^2), but your current algorithm runs in O(n^3) because GetDistanceIndex() always starts from scratch. Also, I wouldn't use lists and dictionaries, try to use a simple array, so that you can access and delete elements in constant time. Deleting from a list can be inefficient, it never gets better than O(log(n)).

At the moment, that's the only optimization I can think of, maybe someone will have a better idea.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

{1,9,2,8,3,7,4,6,5} seems to conform to your requirements, and is fairly easy to generate.

Just sort the numbers in ascending / descending order (if not already done).

Then iterate from both the back and the front, alternating between them until we get to the middle. This step runs in linear time.

Improve this answer

1 Comment

except that 3d element will be always close to element 1 etc, which I'd also like to avoid. Ideally for me, after 9 would come 5

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.