java - 排列数组元素最大化距离 vector Java

Question

假设 v = [0, 1, 2, 3, 4] ，我需要对其进行排列，以便新索引 每个元素都尽可能远。我的意思是，最小化距离 vector 的方差，同时最大化。例如，作为距离 vector 的d:

Opt 1 -> [0, 4, 1, 3, 2], d = [3, 2, 1, 0] -> 不行!它不是统一的。
Opt 2 -> [0, 1, 2, 3, 4], d = [0, 0, 0, 0] -> 不行!它是统一的，但不是格言。
Opt 3 -> [0, 2, 4, 1, 3], d = [1, 1, 2, 1] -> 也许不错的选择，我不知道它是否是最好的。 ..

有一些算法/过程/想法可以做到这一点吗？我必须用 Java 来做，也许存在一些 构建方法来做到这一点，但我没有找到它...

Answer 1

为了能够发布我的小测​​试程序，我现在发布一个答案。

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("}");
        }
}

由于算法的复杂度为 O(n)(n 是 vector 大小)，这也适用于(非常)大的集合。 (如果必须先对输入进行排序，则复杂度为 n log(n))。

正如这个小程序所证明的，我最初的想法 (reorder1) 不会给出关于距离的最佳结果。所以 reorder2() 将是我选择的算法。 (它简单、快速并且提供了可接受的结果，就像它看起来那样)。

使用的测试值是我最喜欢的一些数字。还有一些 ;-)