置换数组元素最大限度地利用距离向量Java

Question

假设v = [0, 1, 2, 3, 4]，我需要改变它，以便每个元素的新索引尽可能远。我的意思是，距离向量中的方差最小，同时也是最大的。例如，距离向量为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] ->也许是个好选择，我不知道这是不是最好的.

有一些algorithm/procedure/idea可以这样做吗？我必须用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是向量大小)，这也适用于(非常)大的集合。(如果必须先对输入进行排序，则复杂性为n log(n))。

正如这个小程序所证明的，我最初的想法(reorder1)在距离方面不会产生最好的效果。因此，reorder2()将是我选择的算法。(它简单，快速，并提供了可接受的结果，就像它看起来)。

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

Answer 2

如果我正确理解了这个问题，您想要创建最大和最均匀的距离数组。

蛮力

不幸的是，我认为这个问题是NP难的，这意味着，如果它绝对必须是最优的解决方案，你可能会更好地循环通过所有可能的排列数组和选择最好的。如果您有一个相对较小的数组，这实际上可能是您的最佳选择。

使用蛮力寻找最佳解决方案的伪代码如下：

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

getScore表示如何确定什么构成“最佳数组”。我看到，在您提供的最佳解决方案中，在其他距离值1中有一个"2“，这意味着您容忍具有非均匀答案的解。我的建议是，将所有距离相加，并减去与最常见的距离不同的每一段距离的惩罚。减去多少将决定它们是否都是统一的(进行一些尝试和错误以了解什么是最有效的)。

遗传算法

如果您想要一个非常好的解决方案，但不一定是最好的解决方案，那么您应该考虑使用遗传算法。

如果你是Java新手，我道歉！如果您是Java新手，这绝对不是最好的开始。

遗传算法的思想是创建一个列表排序的总体(可以是一个索引列表)。它不需要保持每一个可能的组合，只是大约50左右。使用算法的每一个回合，您将评估每个解决方案的“分数”(相当于上面提到的getScore )。然后，50/2次，你随机选择两个有加权概率的解，这些解有较高的分数，你从两个父解中创建两个新的解。然后你有一个新的群体，然后你可以执行另一个回合，以此类推。

如果你继续这样做，通常会出现这样的趋势:你会看到人口中的分数有所提高，如果做得好，这些解决方案也会得到改善。考虑总是直接包括解决方案与最好的分数在每个回合，否则你有风险失去你的最佳解决方案在每一轮。

模拟退火

模拟退火是稍微修改解决方案以改进或恶化解决方案的过程。如果它恶化了，那么你保留以前的解决方案。如果改进了，就保留新的解决方案。在这两种情况下，您都会继续修改解决方案，直到对解决方案的任何更改都不会带来更好的解决方案。这是一个非常简单的算法，但它至少可以找到一个局部最大值。

在您的情况下，您要做的更改将是列表排序。比方说，不要使用列表排序0,1,2,3，你可以尝试0,2,1,3，你会发现它的分数更好。保持0,2,1,3，然后尝试修改其他内容。

我希望这能帮上忙！

Answer 3

如果向量的维数n是奇数，问题就很容易解决。然后d= (n -1)/2是n的素数，你只需构建一个星形多边形(d，n)(见维基百科上的星星多边形或星图)。同样的事情是添加距离d(模n)。如果维数为偶数且d= n /2-1为素数，则相同的方法.如果不是更复杂的话。但我承认，这是圆形问题的解(其中考虑了最后一个元素与第一个元素之间的距离)。例如:对于1à9，距离4，我们得到: 1,5,9,4*,8,3*,7,2*,5 (* 4= 13 (模9)，id表示其他*)。距离是常数和最大值(从圆形的角度来看)，

Brg