The Unique Permutations Algorithm with Duplicate Elements

  • Time：2020-09-17 14:26:24
  • Class：Weblog
  • Read：19

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

Example:

Input: [1,1,2]
Output:

1
2
3
4
5

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

How to Get Unique Permuations in C++?

In fact, the C++ STL algorithm header provides the std::next_permutation() which deals with the duplicate elements in the candidate array. We just need to sort the array, then start permutating until the next_permutation() returns false.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> r;
        sort(begin(nums), end(nums));
        r.push_back(nums);
        while (next_permutation(begin(nums), end(nums))) {
            r.push_back(nums);
        }
        return r;
    }
};
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> r;
        sort(begin(nums), end(nums));
        r.push_back(nums);
        while (next_permutation(begin(nums), end(nums))) {
            r.push_back(nums);
        }
        return r;
    }
};

Recursive Permutation Algorithm without Duplicate Result

Similar to The Permutation Algorithm for Arrays using Recursion, we can do this recursively by swapping two elements at each position. However, we need to keep tracking of the solution that has also been in the permutation result using a hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> r;
        dfs(nums, 0, r, "");
        return r;
    }
    
private:
    unordered_set<string> used;
    void dfs(vector<int>& nums, int index, vector<vector<int>> &r, string key) {
        if (index == nums.size()) {
            if (!used.count(key)) {
                r.push_back(nums);
                used.insert(key);
            }            
        } else {
            for (int i = index; i < nums.size(); ++ i) {
                swap(nums[i], nums[index]);
                dfs(nums, index + 1, r, key + std::to_string(nums[index]));
                swap(nums[i], nums[index]);
            }
        }
    }
};
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> r;
        dfs(nums, 0, r, "");
        return r;
    }
    
private:
    unordered_set<string> used;
    void dfs(vector<int>& nums, int index, vector<vector<int>> &r, string key) {
        if (index == nums.size()) {
            if (!used.count(key)) {
                r.push_back(nums);
                used.insert(key);
            }            
        } else {
            for (int i = index; i < nums.size(); ++ i) {
                swap(nums[i], nums[index]);
                dfs(nums, index + 1, r, key + std::to_string(nums[index]));
                swap(nums[i], nums[index]);
            }
        }
    }
};

In the worst cases, both implementations are O(N!) as N! is the total number of permutation results for N-size elements.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
Customizing WordPress with Branda by WPMU DEV
How to Blog Like Shakespeare
Depth First Search Algorithm to Delete Insufficient Nodes in Roo
C/C++ Program to Compute the Angle Between Hands of a Clock
What Should Your Anti Virus Software Have in Order to Be Effecti
The Importance of SEO and How They Improve the Number of Your Cl
Learn The Basics Of Google My Business
Iterative and Recursion Algorithms to Compute the Number of Step
How to Check if a DLL or EXE is 32-bit or 64-bit (x86 or x64) us
C++: How to Iterate the Elements over the Sets (set, unordered_s
Share：Facebook Twitter
Comment list
Comment add