1

Suppose v = [0, 1, 2, 3, 4] , I need to permute it so that the new indices of each element are as distant as possible. I mean, minimizing the variance in the distance vector and, at the same time, maxim. For example, being d the distance vector:

Opt 1 -> [0, 4, 1, 3, 2], d = [3, 2, 1, 0] -> NO OK! It isn't uniform.
Opt 2 -> [0, 1, 2, 3, 4], d = [0, 0, 0, 0] -> NO OK! It's uniform but not maxim.
Opt 3 -> [0, 2, 4, 1, 3], d = [1, 1, 2, 1] -> Maybe good option, I don't know if it's the best...

There is some algorithm/procedure/idea to do that? I've to do it in Java, maybe exist some built method to do that, but I don't find it...

Improve this question
22
  • I think the primary issue here is understanding the problem. Can you rephrase what you mean? Could you tell us what would be the optimal value for this array (if it is too complicated to solve, try with a simpler array perhaps)? Commented Feb 14, 2014 at 13:19
  • In fact 3rd option is the best in this example. I meant that it isn't unique, d = [1,2,1,1] is another one... uniqueness isn't a problem. Sorry about "Maybe good option", actually is the best option. Commented Feb 14, 2014 at 13:29
  • 1
    @Amanda: So I understood in the mean time. Although I don't understand why you keep subtracting 1. Does the distance between x and x equal -1 ??? Commented Feb 14, 2014 at 14:04
  • 1
    @Amanda: although you might have a solution now, I have another question: Is the idea to maximize the distance first and then take care of the uniformity, or the other way around? In other words, what's better: |d| = 10, u = 3 or |d| = 12, u = 7? (Thereby: |d| is the length of the distance vector, u is the variance in the distance vector). Or do you have some formula which makes the pair measurable? Commented Feb 15, 2014 at 12:26
  • 1
    So far I've been thinking more theoretically about the problem. I didn't prove it yet, but to me it seems obvious that if the vector is sorted, |d| will be minimal. Now if you take the highest value in the vector and put it in the middle of a new vector. Then you take the two smallest values and put those each on one side of the first value. Next you take the two highest values and then again the lowest values. And so on. That should give a quite maximized |d|. It might even be the absolute maximum. But the variance will be horrible. Without a rule for a trade off, I'm pretty stuck now. Commented Feb 16, 2014 at 12:27

3 Answers 3

Reset to default
1

In order to be able to post my little test program, I post an answer now.

import java.util.*; class x { static final int testseries[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }; public static void main(String argv[]) { Vector orig = new Vector(); for (int i = 0; i < testseries.length; ++i) orig.add(new Integer(testseries[i])); Vector dist = getD(orig); System.out.println("d min = " + getAbsD(dist) + "\tUniformity = " + getUniformity(dist)); printVector(orig); printVector(dist); System.out.println(); Vector v = reorder1(orig); dist = getD(v); System.out.println("d = " + getAbsD(dist) + "\tUniformity = " + getUniformity(dist)); printVector(v); printVector(dist); System.out.println(); v = reorder2(orig); dist = getD(v); System.out.println("d = " + getAbsD(dist) + "\tUniformity = " + getUniformity(dist)); printVector(v); printVector(dist); System.out.println(); return; } // // This method constructs the Distance Vector from the input // public static Vector getD(Vector orig) { Vector v = new Vector(); for (int i = 0; i < orig.size() - 1; ++i) { int a = ((Integer) orig.get(i)).intValue(); int b = ((Integer) orig.get(i + 1)).intValue(); v.add(new Integer(Math.abs(a - b))); } return v; } public static double getAbsD(Vector orig) { double d = 0; Vector v = getD(orig); for (int i = 0; i < v.size(); ++i) { int a = ((Integer) v.get(i)).intValue(); d += a * a; } return Math.sqrt(d); } public static double getUniformity(Vector dist) { double u = 0; double mean = 0; for (int i = 0; i < dist.size(); ++i) { mean += ((Integer) dist.get(i)).intValue(); } mean /= dist.size(); for (int i = 0; i < dist.size(); ++i) { int a = ((Integer) dist.get(i)).intValue(); u += (a - mean) * (a - mean); } return u / dist.size(); } // // This method reorders the input vector to maximize the distance // It is assumed that the input is sorted (direction doesn't matter) // // Note: this is only the basic idea of the distribution algorithm // in this form it only works if (n - 1) mod 4 == 0 // public static Vector reorder1(Vector orig) { Integer varr[] = new Integer[orig.size()]; int t, b, lp, rp; t = orig.size() - 1; b = 0; lp = t / 2 - 1; rp = t / 2 + 1; varr[t/2] = (Integer) orig.get(t); t--; while (b < t) { varr[lp] = (Integer) orig.get(b); b++; varr[rp] = (Integer) orig.get(b); b++; lp--; rp++; varr[lp] = (Integer) orig.get(t); t--; varr[rp] = (Integer) orig.get(t); t--; lp--; rp++; } Vector result = new Vector(); for (int i = 0; i < orig.size(); ++i) result.add(varr[i]); return result; } // // This method reorders the input vector to maximize the distance // It is assumed that the input is sorted (direction doesn't matter) // // Note: this is only the basic idea of the distribution algorithm // in this form it only works if (n - 1) mod 4 == 0 // public static Vector reorder2(Vector orig) { Integer varr[] = new Integer[orig.size()]; int t, b, lp, rp; t = orig.size() - 1; b = orig.size() / 2 - 1; lp = t / 2 - 1; rp = t / 2 + 1; varr[t/2] = (Integer) orig.get(t); t--; while (b > 0) { varr[lp] = (Integer) orig.get(b); b--; varr[rp] = (Integer) orig.get(b); b--; lp--; rp++; varr[lp] = (Integer) orig.get(t); t--; varr[rp] = (Integer) orig.get(t); t--; lp--; rp++; } Vector result = new Vector(); for (int i = 0; i < orig.size(); ++i) result.add(varr[i]); return result; } // // to make everything better visible // public static void printVector(Vector v) { String sep = ""; System.out.print("{"); for (int i = 0; i < v.size(); ++i) { System.out.print(sep + v.get(i)); sep = ", "; } System.out.println("}"); } }

Since the complexity of the Algorithm is O(n) (n is the vector size) this will work for (very) large sets too. (If the input has to be sorted first, complexity is n log(n)).

As this little program proves, my original idea (reorder1) won't give the best result with respect to the distance. So reorder2() would be the algorithm of my choice. (It's simple, fast and delivers acceptable results, as it seems).

The test values used are some of my favourite numbers. There exist a few more ;-)

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

3 Comments

Thank you @Ronald, reorder2 is a great and simple solution. (...and yes, there exist infinitely more :))
reorder1 and reorder2 have some problem in which the last element is not inserted, and a NullPointerException is thrown in getD when it tries to handle it.
That's why I wrote in the comment that it's just the idea of the algorithm, only working for specific n ((n - 1) mod 4 == 0). So it's more like a proof of concept than production proof. But it should be comparatively easy to implement a similar algorithm for other n. (n even, (n - 1) mod 4 == 2). Anyway, the program as printed works in my environment.
1

If I understand the problem correctly, you want to create the maximum and most uniform distance array possible.

Brute force

Unfortunately I believe this problem is NP-hard, meaning if it absolutely has to be the optimal solution, you may be better off cycling through all possible permutations of the array and picking the best. If you have a relatively small array, this may, in effect, be your best bet.

The pseudocode for finding the best solution using brute force would be something like:

var max = MIN; for each permutation of array var score = getScore(permutation) if(score > max) max = score; end

getScore represents how you determine what makes up a "best array". I saw that in your best solution for what you provided, there was a "2" among the other distance values of 1, which means you tolerate solutions with non-uniform answers. My suggestion would be something along the lines of adding up all distances and subtracting a penalty for each distance which varies from the most common. How much you subtract will determine how important it is that they are all uniform (perform some trial and error to understand what works best).

Genetic algorithms

If you want a really good solution, but not necessarily the best, then you should consider using genetic algorithms.

If you're new to Java, I apologize! This is definitely not the best thing to start off with if you're new to Java.

The idea behind genetic algorithms is that you create a population of list orderings (could be a list of indexes). It doesn't have to hold every possible combination, just around 50 or so. With each turn of the algorithm, you evaluate each solution's "score" (equivalent of getScore mentioned above). Then, 50/2 times, you randomly select two solutions with weighted probability favoring those solutions which had a higher score and you create two new solutions from the two parent solutions. You then have a new population which you can then perform another turn, and so forth and so on.

If you continue in this way, often the trend emerges that you will see scores improve in the population and if done properly, these solutions will improve as well. Consider always directly including the solution with the best score in each turn, or you risk to lose your very best solution at each turn.

Simulated annealing

Simulated annealing is the process of modifying a solution slightly in order to improve or worsen a solution. If it worsens, then you keep the solution you had before. If it improves, you keep the new solution. In either case, you continue to modify the solution until no change to the solution brings a better one. This is a very simple algorithm, but it is guaranteed to find you at least a local maximum.

In your case, the changes you would be making would be the list ordering. Say rather than use list ordering 0,1,2,3, you try 0,2,1,3 and you find its score is better. You keep 0,2,1,3, and you try to modify something else.

I hope that helps!

Improve this answer

5 Comments

Thank you @Neil, I had to program some genetic algorithms fitness based at university and it isn't solution to my problem, I mean, it's solution, but I only want mess a list, not worth it! :D Brute force is not option at all, mess the list is a small part of a big process that must be fast... Maybe it isn't possible mess it the best way.
@AmandaGarci I expanded my answer to include simulated annealing. Please take a look. This may not offer the best solution, but this is a quick way to go about it.
I believe you mean NP-complete or NP-hard. NP just means verifiable in polynomial time.
@Dukeling You're right, I did mean NP-hard. I don't think it is possible to verify that a solution is optimal in polynomial time. Made the proper adjustments.
Thank you @Neil, simulated annealing is likely the best solution.
0

IMHO the problem is quite easy if the dimension n of your vector is odd. Then d = (n -1)/2 is prime with n and you just have to build a star polygon (d, n)(see stars polygons or stellation on wikipedia). Same thing is to add the distance d (modulo n). If the dimension is even and if d = n/2 - 1 is prime with n, same method. More complications if not. But I confess that it is the solution of the circular problem (where the distance among the last element and the first one is also taken in account). Example : for 1 à 9, distance 4, we obtain : 1,5,9,4*,8,3*,7,2*,5 (* 4 = 13 (modulo 9), id for the others *). The distance is constant and max (in the circular point of view),

Brg

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.