The Unique Permutations Algorithm with Duplicate Elements

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

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

推荐阅读：
加权平均数是什么意思？　 四舍五入法怎么用　 多边形的内角和公式　 梯形上底的定义是什么　 用放大镜看角变大了吗　 四位一级和三位分节　 求近似数的方法有哪几种　 自然数的产生　 有没有平方十米　 二进制和十六进制　
评论列表
添加评论