語境
我正在嘗試撰寫一個演算法來解決以下問題：
給定一個可能包含重復的數字集合 nums，以任何順序回傳所有可能的唯一排列。
我對演算法的想法源于您如何解釋 k 集的排列數等于 k！：我將第一個元素放置在新陣列的所有 k 個位置中，并且對于每個位置，我將下一個元素放置在所有可用的剩余位置等，直到最后一個元素。我遞回地執行此操作，并將字典傳遞給此遞回函式，以記住哪個位置可用于下一個元素。因為原始陣列中可能有重復的元素，所以我使用一個集合來添加我在演算法中提出的排列，并確保它們在集合中是唯一的。當所有元素都已放置時，將添加排列。到目前為止，我提出了以下演算法：
public class Solution {
public HashSet<int[]> permutations = new HashSet<int[]>();
public IList<IList<int>> PermuteUnique(int[] nums) {
int[] permutation = new int[nums.Length];
Dictionary<int, bool> posTaken = new Dictionary<int, bool>();
for (int i = 0; i < nums.Length; i ) {
posTaken.Add(i, false);
}
f(nums, 0, permutation, posTaken);
return new List<IList<int>>(permutations);
}
private void f(int[] nums, int index, int[] permutation, Dictionary<int, bool> posTaken) {
Console.WriteLine("index " index);
if (index == nums.Length) {
Console.WriteLine("hey");
permutations.Add(permutation);
return;
}
for (int i = 0; i < nums.Length; i ){
if (!posTaken[i]) {
Console.WriteLine("i " i);
Dictionary<int, bool> posTakenCopy = new Dictionary<int, bool>(posTaken);
int[] permutationCopy = new int[nums.Length];
permutation.CopyTo(permutationCopy, 0);
permutationCopy[i] = nums[index];
Console.WriteLine(string.Join(", ", posTakenCopy.Select(a => $"{a.Key}: {a.Value}")));
Console.WriteLine("[{0}]", string.Join(", ", permutationCopy));
posTakenCopy[i] = true;
f(nums, index , permutationCopy, posTakenCopy);
}
}
}
}
這個想法可能不是解決它的最佳方法，但我仍在草稿程序中只是測驗東西，當我嘗試運行代碼時，我偶然發現了兩個我真的不明白的問題。
問題
發生在假定的所有有效輸入中。下面的輸出對應于這個輸入：[1, 2, 3]。
運行時錯誤
首先，我收到以下錯誤：
未處理的例外。System.IndexOutOfRangeException：索引超出了陣列的范圍。 第 15 行：Solution.cs 中的 Solution.f(Int32[] nums, Int32 index, Int32[] permutation, Dictionary
2 posTaken) in Solution.cs Line 31: Solution.f(Int32[] nums, Int32 index, Int32[] permutation, Dictionary2 posTaken) 第 10 行：Solution.cs 中的 Solution.PermuteUnique(Int32[] nums) 第 33 行：Driver .Main驅動程式.cs中的 (String[] args)
我列印了此代碼中用作陣列索引的所有變數，并且列印的值總是低于陣列的長度！我肯定忽略了一些東西。
令人驚訝的控制臺輸出
這是使用 nums = [1, 2, 3] 列印到控制臺的輸出。
index 0
i 0
0: False, 1: False, 2: False
[1, 0, 0]
index 0
i 1
0: True, 1: False, 2: False
[1, 1, 0]
index 0
i 2
0: True, 1: True, 2: False
[1, 1, 1]
index 0
i 2
0: True, 1: False, 2: False
[1, 0, 2]
index 1
i 1
0: True, 1: False, 2: True
[1, 2, 2]
index 1
i 1
0: False, 1: False, 2: False
[0, 2, 0]
index 1
i 0
0: False, 1: True, 2: False
[2, 2, 0]
index 1
i 2
0: True, 1: True, 2: False
[2, 2, 2]
index 1
i 2
0: False, 1: True, 2: False
[0, 2, 3]
index 2
i 0
0: False, 1: True, 2: True
[3, 2, 3]
index 2
i 2
0: False, 1: False, 2: False
[0, 0, 3]
index 2
i 0
0: False, 1: False, 2: True
[3, 0, 3]
index 2
i 1
0: True, 1: False, 2: True
[3, 3, 3]
index 2
i 1
第三個字典輸出對我來說沒有任何意義。這里的“索引”表示原始陣列中元素的位置，我們在所有位置移動以構建我們的下一個排列。放置之后，我們在字典 posTaken 中記錄下一個元素（作為布林值）可以使用的位置，然后再重復相同的程序。所以基本上，當 index == 0 時，應該只有一個 True，所有其他條目都應該是 False。但是字典的第三個列印顯示 2 個條目 False！在我看來， position_taken 字典和排列陣列沒有正確克隆。我在這里做錯了什么？
此外，對我來說最重要的是，我完全不知道為什么按以下順序列印索引：0、0、...、1、1、...、2、2、...、2。看起來就像它正在執行 BFS 而它應該執行 DFS，例如：為什么不列印這樣的索引：0、1、2、0、1、2 等。
uj5u.com熱心網友回復：
我的錯：
index：我需要將值復制到另一個變數中以獲得適當的行為。HashSet<int[]>沒有表現得像我想象的那樣。根據這篇文章，HashSet 使用GetHashCode()andEquals()來比較兩個物件。我需要比較兩個陣列的內部值以確定它們的相等性，因此之前的實作無法正常作業。我選擇使用HashSet<string>，并將陣列轉換為字串，以便充分比較它們。
下面的代碼雖然不是最好的性能，但可以作業：
public class Solution {
public HashSet<string> permutationsSet = new HashSet<string>();
public List<int[]> permutations = new List<int[]>();
public IList<IList<int>> PermuteUnique(int[] nums) {
int[] permutation = new int[nums.Length];
Dictionary<int, bool> posTaken = new Dictionary<int, bool>();
for (int i = 0; i < nums.Length; i ) {
posTaken.Add(i, false);
}
f(nums, 0, permutation, posTaken);
return new List<IList<int>>(permutations);
}
private void f(int[] nums, int index, int[] permutation, Dictionary<int, bool> posTaken) {
if (index == nums.Length) {
if(permutationsSet.Add(string.Join("", permutation))) {
permutations.Add(permutation);
};
return;
}
for (int i = 0; i < nums.Length; i ){
if (!posTaken[i]) {
Dictionary<int, bool> posTakenCopy = new Dictionary<int, bool>(posTaken);
int[] permutationCopy = new int[nums.Length];
permutation.CopyTo(permutationCopy, 0);
permutationCopy[i] = nums[index];
posTakenCopy[i] = true;
int indexCopy = index 1;
f(nums, indexCopy, permutationCopy, posTakenCopy);
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/475124.html