Context
I am trying to write an algorithm to solve the following problem:
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
My idea for an algorithm derives from how you explain the number of arrangements of a k-set is equal to k!: I place the first element in all k position of a new array and for each position I place the next element in all of the available remaining positions etc until the last element. I do this recursively, and I pass to this recursive function a dictionary to memorize which position is available for the next element. Because there can be duplicate elements in the original array, I use a set to add the permutations I come up with in the algorithm and ensure they are unique in the set. The permutations are added when all elements have been placed. So far I've come up with the following algorithm:
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);
}
}
}
}
This idea may not be the optimal way to solve it but I am still in the draft process just testing stuff, and as I tried to run the code I stumbled upon two issues that I really don't understand.
The problems
Occur for supposedly all valid inputs. The output below corresponds to this input: [1, 2, 3].
A runtime error
First I get the following error:
Unhandled exception. System.IndexOutOfRangeException: Index was outside the bounds of the array. Line 15: 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) in Solution.cs Line 10: Solution.PermuteUnique(Int32[] nums) in Solution.cs Line 33: Driver.Main(String[] args) in Driver.cs
I print all variables that are used as indexes for the arrays in this code and the values printed are always inferior to the length of the array! I surely overlooked something.
A surprising console output
This is the output printed to the Console with 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
The third dictionary output doesn't make any sense to me. Here "index" denotes the position of the element in the original array that we are moving in all positions to build our next permutation. After we placed it, we record in the dictionary posTaken which positions are available for the next element (as a boolean) before we repeat the same process. So basically, when index == 0, there should only be one True and all other entries should be False. But the third print of the dictionary shows 2 entries False! It seems to me the position_taken dictionary and the permutation array are not cloned properly. What did I do wrong here?
Additionally and most importantly for me, I am completely clueless as to why the indexes are printed in this order: 0, 0, ..., 1, 1, ..., 2, 2, ..., 2. It looks like it is doing a BFS while it should be doing a DFS, as in: why aren't the indexes printed like this: 0, 1, 2, 0, 1, 2 etc.
CodePudding user response：
My mistakes:
index: I needed to copy the value into another variable to get the appropriate behaviour.HashSet<int[]>did not behave like I thought it would. As per this post, HashSet usesGetHashCode()andEquals()to compare two objects. I needed to compare the inner values of both arrays to determine their equality, so the previous implementation could not work. I opted to useHashSet<string>instead, and convert the arrays to strings in order to compare their adequately.
The code below, while not the best performance wise, works:
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);
}
}
}
}