The Unique Permutations Algorithm with Duplicate Elements

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

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

推荐阅读：
保健食品需谨慎 所谓效果是心理作用　 关于预防癌症的十条饮食和生活建议　 春季喝蜂蜜功效胜补品抗过敏润肺止咳　 这十种食用方法让蜂蜜营养又健康　 婴幼儿等四类人群不宜食用蜂蜜　 教你这七招快速辨别蜂蜜的真假　 舌尖上的中国之虾子面背后的故事　 豆浆和什么食物一起搭配吃更健康　 家庭制作豆浆的步骤及豆浆搭配宜忌　 怎么喝啤酒健康养生及饮用啤酒禁忌　
评论列表
添加评论