c＃递归函数以循环为错误的顺序？

Question

上下文

我试图编写一种算法来解决以下问题：

给定数字的集合，数字，可能包含重复项，以任何顺序返回所有可能的唯一排列。

我对算法的想法源于您如何解释k-stet的排列数量等于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.f（int32 [] nums，int32 index，int32 []置换，词典postaken中的字典postaken）。 ，词典 2 postaken）在解决方案中 第10行：solution.permuteunique（int32 [] nums） 第33行：驱动程序。驱动程序 .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

第三个字典输出对我来说没有任何意义。这里的“索引”表示元素在原始数组中的位置，我们在所有位置上移动以构建我们的下一个排列。放置它后，我们在词典中记录了下一个元素（作为布尔值）的位置，然后再重复相同的过程。因此，基本上，当索引== 0时，应该只有一个true，所有其他条目应为false。但是词典的第三张打印显示了2个条目false！ 在我看来，位置词字典和排列阵列未正确克隆。我在这里做错了什么？

另外，最重要的是，我完全毫无疑问地以此顺序打印索引：0、0，...，1、1，...，2、2，...，2。就像它在做dfs时正在执行BFS一样，如：为什么没有像这样打印的索引：0、1、2、0、1、2等。

Answer 1

我的错误：

1. 索引++：我需要将值复制到另一个变量中以获得适当的行为。

2. HashSet＆lt; int []＆gt;的行为不像我想的那样。根据此 /code>和equals（）比较两个对象。我需要比较两个数组的内部值以确定它们的平等性，以便先前的实现无法正常工作。我选择使用HashSet＆lt; string＆gt;，然后将数组转换为字符串以进行足够的比较。

   
   

下面的代码虽然不是最佳性能，但可行：

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