for循环中的C#递归函数以错误的顺序调用？

Question

上下文

我正在尝试编写一个算法来解决以下问题：

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

我对算法的想法源自您如何解释 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].

一个运行时间错误

首先我得到以下错误：

Unhandled exception. System.IndexOutOfRangeException: Index was outside the bounds of the array. Line 15: Solution.f(Int32[] nums, Int32 index, Int32[] permutation, Dictionary2 posTaken) in Solution.cs Line 31: Solution.f(Int32[] nums, Int32 index, Int32[] permutation, Dictionary2 posTaken) in Solution.cs Line 10: Solution.PermuteUnique(Int32[] nums) in Solution.cs Line 33: Driver.Main(String[] args) in Driver.cs

我打印了这段代码中用作数组索引的所有变量，打印的值总是低于数组的长度！我肯定忽略了什么。

令人惊讶的控制台输出

这是打印到控制台的输出，其中 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 个词条是假的！在我看来 position_taken 字典和排列数组没有正确克隆。我这里做错了什么？

此外，对我来说最重要的是，我完全不知道为什么索引会按以下顺序打印：0, 0, ..., 1, 1, ..., 2, 2, ... , 2. 看起来它在做 BFS 而它应该在做 DFS，如： why aren't the indexes printed like this: 0, 1, 2, 0, 1, 2 etc.

Answer 1

我的错误：

index++：我需要将值复制到另一个变量以获得适当的行为。
HashSet<int[]>并没有像我想象的那样表现。根据这个 post，HashSet 使用 GetHashCode() 和 Equals() 来比较两个对象。我需要比较两个数组的内部值以确定它们是否相等，因此之前的实现无法工作。我选择使用 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);
            }
        }
    }
}

for循环中的C#递归函数以错误的顺序调用？

C# recursive function in for loop is called in the wrong order?

c#

recursion

for-loop

clone

上下文

问题

一个运行时间错误

令人惊讶的控制台输出