帶列表的Java遞歸<int[]> .add（）重複值

我試圖在遞歸方法中將int[]添加到List<int[]>時遇到了一些問題。我得到N大小的int[]的所有排列組合以用於不同的功能。我想要將中的每一個添加到前面提到的列表中。然而，似乎並不是所有排列都可以添加int []（shortestPath），並且說實話我沒有足夠的遞歸經驗來知道爲什麼每個數組的打印輸出能夠工作，但添加到列表中只需添加第一個arr（作爲參數傳遞的那個）6次。帶列表的Java遞歸<int[]> .add（）重複值

我的代碼如下：

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

附： - 打印輸出僅用於快速查看數據結構的狀態。當實現功能完全正常時，它們當然會被刪除:)而且，這些代碼嵌套在一個類中，該類中有更多與矩陣處理相關的功能。該函數特別是最短路徑算法的輔助函數。

在此先感謝那些瞭解遞歸比我更好，誰願意幫助！

Chris

來源

2013-04-11 Chris Cirefice

您正在修改和添加參考給你打電話add同一陣列arr每次。你應該創建一個新的數組，交換，然後將其添加到列表中。

UPDATE：更詳細一點..

您在主創建一個新的數組arr，然後通過參考（由值）與permute功能。在else部分中，您將交換數組引用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. 
}

有可能是一個更好的辦法，但我不是專家任。

更新2： 活生生的例子.. http://ideone.com/vHcz7b

_{P.S：有人可以格式化這個給我嗎？}

來源

2013-04-11 01:52:41 vidit

謝謝你的建議。我現在明白爲什麼複製是必要的，我已經做了修改，以反映在我的代碼中。現在有50％的工作。如果你運行該方法，你會注意到輸出如下：'1，2，3'，'1，2，3'，'2，1，3'，'2，1，3'，'3 ，2,1'，'3,2,1'。這並不完全陌生，我相信它與交換語句之一有關，但我無法弄清楚爲什麼它不會交換每對重複中的集合。我一直盯着這一段時間，但也許這只是一個明顯的錯誤，我只是看了一眼...... – 2013-04-11 02:39:14

@ChrisCirefice - 我已經添加了一個活的例子..希望有所幫助。 – vidit 2013-04-11 02:49:17

好的，我修好了！這是交換操作，第二個是具體的。我製作了int []的「前置換」副本，並且交換了複製數組的值，但我應該已經交換了原始值（同時交換「forward」複製數組的值）...有道理？無論如何，我會在此評論後更新代碼以反映這些更改。希望有人在將來遇到這個問題，並發現我的代碼和你的副本想法很有幫助！噢，我現在明白'null'的意思了......這也行得通：P – 2013-04-11 02:55:04

Here是置換碼的幾個例子，希望能幫助你

來源

2013-04-11 01:53:01

請記住，數組是一個對象。這意味着參數arr是對該對象的引用。每次遞歸調用都會引用相同的數組，因此任何更改都會反映在使用對該數組的引用的任何位置。這也意味着每次您撥打shortestPaths.add(arr);時，您都會反覆添加對同一陣列的引用。所以你的列表將包含許多對同一個數組對象的引用。這就是說，爲了做你想做的事情，你需要在每次你想做一個改變時創建一個數組的副本，並將它添加到你的List。

來源

2013-04-11 01:54:47

帶列表的Java遞歸<int[]> .add（）重複值

回答

相關問題