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

第三部分 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，但它们应该匹配。

Answer 2

来自 Arrays.copyOfRange docs，参数为：

• original - 要从中复制范围的数组
• - 要复制的范围的初始索引，包括
• -要复制的范围的最终索引，不包括在内。 （该索引可能位于数组之外。）

因此您应该有以下四行：（起始/起始索引不应递增）

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

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

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

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

问候，
史蒂芬

Answer 3

尝试 Arrays.copyOfRange(temp, pos1, pos2); 等，而不在开始参数中添加 1。

Answer 4

在上面的代码中，

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

在part1= Arrays.copyOfRange(temp, 0, pos1);中，数组被复制到pos-1
而在第2部分= Arrays.copyOfRange(temp, pos1+1, pos2); ， pos1 处的元素被忽略，因为部分复制的数组是从 pos1+1 开始的