Разделение массива 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, 351, 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 4912 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

Проблема в том, что 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 равен exclusive . Это типично для API Java - например, "012345".substring(0, 3) даст вам «012», а не «0123».

Это не часть part2, потому что вы начинаете с pos1+1.

По сути, два аргумента должны совпадать. Не ясно, должны ли они оба быть pos1 + 1 или pos1, но они должны совпадать.

Answer 2

В приведенном выше коде

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, а в part2 = Arrays.copyOfRange (temp,pos1 + 1, pos2);элемент в позиции pos1 не учитывается, так как частично копируемый массив начинается с позиции pos1 + 1

Answer 3

С Arrays.copyOfRange docs , параметры:

• оригинал - массив, из которого должен быть скопирован диапазон
• from - начальный индекс диапазона, который будет скопирован, включительно
• to - окончательный индекс диапазона, который будет скопирован, исключая. (Этот индекс может находиться вне массива.)

Таким образом, вы должны иметь следующие четыре строки: (индексы start / from не должны увеличиваться)

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

С уважением, Stéphane

Answer 4

Попробуйте Arrays.copyOfRange(temp, pos1, pos2); и т. Д., Не добавляя 1 к параметру запуска.