Java array splitting and reconnecting. Lost elements

I'm trying to implement the TSP double bridge move which works as follows: Given a permutation(tour) of cities it splits the permutation in 4 parts and reconnects these parts in different order. e.g. perm=[a,b,c,d] ---> [a,d,c,b].

In the following method i have the temp[] array which contains the pemutation's cities. i choose 3 random number and split the array in 4 parts

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

After running the programm an printing the p开发者_如何学Goarts i get.

{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, }LENGTH: 23511950

Positions chosen : 3 12 24

part1 38 18 27

part2 20 35 1 42 50 22 52 36

part3 31 19 33 3 25 29 49 12 4 7 30

part4 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

The problem is that 4 elements are lost. for example: element "2" from the initial permutation doens't exist either in part1 or part2.

So where's the problem?

It's not clear whether you want "2" to be part of part1 or part2, but look at the code:

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

Here, the element at pos1 is not part of part1 because the last argument of copyOfRange is exclusive. This is typical of Java APIs - for example "012345".substring(0, 3) will give you "012", not "0123".

It's not part of part2 because you're starting with pos1+1.

Basically, the two arguments should match. It's not clear whether they should both be pos1 + 1 or pos1, but they should match.

From Arrays.copyOfRange docs, the parameters are :

• original - the array from which a range is to be copied
• from - the initial index of the range to be copied, inclusive
• to - the final index of the range to be copied, exclusive. (This index may lie outside the array.)

So you should have the following four lines : (start/from indexes should not increment)

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

Regards, Stéphane

Try Arrays.copyOfRange(temp, pos1, pos2); etc. without adding 1 to the start parameter.

In the above code

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

In part1= Arrays.copyOfRange(temp, 0, pos1);, the arrays are being copied till pos-1 while in part2= Arrays.copyOfRange(temp, pos1+1, pos2); , the element at pos1 is being left out as the array being copied in part is starting from pos1+1