Q:

Permute array elements maximizing the distance vector Java

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

A:

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

