Java Recursion со списком <int[]> .add() Repeat Values ​​

Question

У меня возникли проблемы с попыткой добавить int[] в List<int[]>, но в рекурсивном методе. Я получаю все перестановки int[] размера N для использования с другой функцией. I хочу, чтобы добавить каждую из этих перестановок в ранее упомянутый список. Однако не кажется, что int [] (shortestPath) может быть добавлен для всех перестановок, и, честно говоря, у меня недостаточно опыта рекурсии, чтобы узнать, почему распечатки каждого массива работают, но добавление в список просто добавляет первый arr (тот, который прошел как параметр) 6 раз.

Мой код выглядит следующим образом:

public int counter = 0; 
public List<int[]> shortestPaths = new ArrayList<int[]>(); 

public void permute(int[] arr, int startIndex) { 

    int size = arr.length; 

    if (arr.length == (startIndex + 1)) { 
     System.out.print("Permutation " + counter + " is: "); 
     for (int i = 0; i < size; i++) { 
      if (i == (size - 1)) System.out.print(arr[i] + "\n\n"); 
      else System.out.print(arr[i] + ", "); 
     } 
     shortestPaths.add(arr); 
     counter++; 
    } else { 
     for (int i = startIndex; i < size; i++) { 
      int[] copy = arr.clone(); 

      int tmp = copy[i]; 
      copy[i] = copy[startIndex]; 
      copy[startIndex] = tmp; 

      permute(copy, startIndex + 1); 

      //tmp = arr[i]; 
      //arr[i] = arr[startIndex]; 
      //arr[startIndex] = tmp; 
      copy = null; 
     } 
    } 
} 

public static void main(String[] args) { 

    int[] arr = { 1, 2, 3 }; 
    permute(arr, 0); 

    System.out.print("\n\n\n\n"); 
    for (int[] a : s.shortestPaths) { 
     System.out.println(a[0] + ", " + a[1] + ", " + a[2] + "\n\n"); 
} 

P.S. - Распечатки доступны только для быстрого просмотра состояния структур данных. Разумеется, они будут удалены, когда реализация будет полностью функциональной :) Кроме того, этот код вложен в класс, который имеет гораздо больше функций, связанных с обработкой матрицы. Эта функция, в частности, является вспомогательной функцией для алгоритма кратчайшего пути.

Заранее благодарим тех, кто знает рекурсию лучше, чем я, и которые готовы помочь!

Chris

Answer 1

Вы изменяете и добавить ссылку на тот же массив arr каждый раз вы называете add. Вы должны создать новый массив, поменять местами и затем добавить его в список.

UPDATE: Чуть более подробно ..

Вы создаете новый массив arr в основной, а затем передать ссылку (по значению) к функции permute. В другой части вы обмениваете два целых числа в ссылке массива arr (вы не создаете новый массив, просто изменяете его) и add его в список. Следующая итерация, то же самое происходит с тем же адресом массива arr, добавив тот же массив снова в список.

Вот что вы должны сделать вместо этого ..

else { 
    int[] tempArr = new int[arr.length]; 
    System.arraycopy(arr, 0, tempArr, 0, arr.length); 

    // swap in the tempArr 
    // add tempArr to the list 
    // after that if you want you can set tempArr to null, to avoid loitering. 
} 

Там может быть лучше, но я не эксперт либо.

Update 2: Живой пример .. http://ideone.com/vHcz7b

_{P.S: Может кто-то форматировать это для меня?}

Answer 2

Here несколько примеров перестановок кода, который мы надеемся, поможет вам

Answer 3

Помните, что массив является объектом. Это означает, что параметр arr является ссылкой на объект. Каждый рекурсивный вызов будет иметь ссылку на тот же массив, чтобы любые изменения отражались везде, где вы используете ссылку на этот массив. Это также означает, что каждый раз, когда вы вызываете shortestPaths.add(arr);, вы добавляете ссылку на тот же самый массив снова и снова. Таким образом, ваш список будет содержать много ссылок на один и тот же объект массива.

С учетом сказанного, чтобы сделать то, что вы хотите, вам нужно сделать копию массива каждый раз, когда вы хотите внести изменения и добавить его в свой List.