Permute array elements maximizing the distance vector Java

Question

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...

Answer 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 ;-)

Answer 2

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!

Answer 3

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