Java 数组拆分和重新连接。丢失的元素

Question

我正在尝试实现 TSP 双桥移动，其工作原理如下:给定城市的排列(游览)，它将排列分成 4 部分，并以不同的顺序重新连接这些部分。例如perm=[a,b,c,d] ---> [a,d,c,b]。

在下面的方法中，我有 temp[] 数组，其中包含排列的城市。我选择 3 个随机数并将数组分成 4 部分

 public void doubleBridge() {
    City[] temp = this.permArray; // it's a tour so the first element equals the last temp[0]=temp[temp.length-1]
    Random  random = new Random();      
    int pos1  = 1+ random.nextInt(temp.length/4);
    int pos2 = pos1 +  1 + random.nextInt(temp.length/4);
    int pos3 = pos2 + 1 + random.nextInt(temp.length/4);
    System.out.println("\nPositions chosen : "+pos1+" "+pos2+" "+pos3);

    City[] part1 = new City[pos1+1];
    part1 = Arrays.copyOfRange(temp, 0, pos1);

    City[] part2 = new City[pos2-pos1-1];
    part2= Arrays.copyOfRange(temp, pos1+1, pos2);

    City[] part3 = new City[pos3-pos2-1];
    part3= Arrays.copyOfRange(temp, pos2+1, pos3);

    City[] part4 = new City[temp.length-1-pos3-1];
    part4= Arrays.copyOfRange(temp, pos3+1, temp.length);

    //City[] newTemp = new City[temp.length];

    System.out.println("\npart1");
    for (City c: part1) {
        System.out.print(c.getId()+" ");
    }


    System.out.println("\npart2");
    for (City c: part2) {
        System.out.print(c.getId()+" ");
    }

    System.out.println("\npart3");
    for (City c: part3) {
        System.out.print(c.getId()+" ");
    }

    System.out.println("\npart4");
    for (City c: part4) {

        System.out.print(c.getId()+" ");
    }
    /*newTemp = concatAll(part1, part2, part3, part4);
    this.permArray = newTemp;
    this.computePermutationLength();*/
}

运行程序后，打印我得到的部分。

{38、18、27、2、20、35、1、42、50、22、52、36、44、31、19、33、3、25、29、49、12、4、7、 30, 43, 24, 48, 45, 26, 39, 11, 15, 21, 34, 28, 8, 13, 51, 41, 17, 10, 37, 46, 32, 16, 23, 14, 5, 9, 6, 47, 40, 38, }长度:23511950

选择的位置:3 12 24

第 1 部分38 18 27

第2部分20 35 1 42 50 22 52 36

第3部分31 19 33 3 25 29 49 12 4 7 30

第 4 部分24 48 45 26 39 11 15 21 34 28 8 13 51 41 17 10 37 46 32 16 23 14 5 9 6 47 40 38

问题是丢失了 4 个元素。例如:初始排列中的元素“2”在第 1 部分或第 2 部分中都不存在。

那么问题出在哪里呢？

Answer 1

不清楚你想要“2”是part1还是part2的一部分，但看看代码:

City[] part1 = new City[pos1+1];
part1 = Arrays.copyOfRange(temp, 0, pos1);

City[] part2 = new City[pos2-pos1-1];
part2= Arrays.copyOfRange(temp, pos1+1, pos2);

此处，pos1 处的元素不是 part1 的一部分，因为 copyOfRange 的最后一个参数是独家。这是典型的 Java API - 例如 "012345".substring(0, 3) 将为您提供“012”，而不是“0123”。

它不是 part2 的一部分，因为您从 pos1+1 开始。

基本上，两个参数应该匹配。尚不清楚它们是否应该都是 pos1 + 1 还是 pos1，但它们应该匹配。