The Unique Permutations Algorithm with Duplicate Elements

  • 时间：2020-09-17 14:26:24
  • 分类：网络文摘
  • 阅读：141 次

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) —

推荐阅读：
How to Improve the Marketing for Your Online Business　 Building an Online Store – What You Need to Do　 Independent Digital Media Is Being Shut Down Around the World, a　 Using the Windows Hardware Tool to Error Checking and Optimize Y　 The Union Find (Disjoint Set) Implementation in Java/C++　 How to use the Leetcode’s Mock Interview Overview to Nail 　 Replace Harddrives when CrystalDiskInfo Shows Caution Health Sta　 Finding the Predecessor and Successor Node of a Binary Search Tr　 Algorithms to Detect Pattern of Length M Repeated K or More Time　 Using the stdout to debug print the solution in the leetcode con　
评论列表
添加评论