LeetCode Permutations I and II: DFS, Swap and Sorting

Overview

3 methods including DFS, Iterative Swap, Recursive Swap are given (pros and cons) to solve LeetCode Permutations problem and use sorting to remove duplicates.

LeetCode Permutations I and II

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2], and [3,2,1].

Further question is if the collection of numbers contain duplicates, how to return all possible unique permutations.

Solution Analysis: DFS, Swap and Sorting

(1) Standard backtracking (DFS) approach

  • Key Idea: for each number, we need an additional array to indicate whether this number is used or not, we can only use those unused numbers to generate the remaining part of the permutation.
  • Remove Duplicate: Sort the input array first so all the duplicates would be continuous. When we try to use the renaming numbers to generate the remaining part of the permutation, say the current number is A[i] and it is not used yet, we need an additional test to check if A[i] is equal to A[i-1], is so, then A[i] is valid to be used (i.e., A[i] could be used without generating duplicates) only if A[i-1] is already used!

The following C++ source code is accepted by LeetCode OJ to pass both Permutation I and II problems:

class Solution {
    public:
        vector<bool> alreadyUsed;
        vector<int>  ans;
        void dfs(int i, int n, vector<vector<int>> *results, const vector<int> &num) {
            if (i >= n) { results->push_back(ans); return ; }
            for (int j = 0; j < n; ++j) {
                if (!alreadyUsed[j]) {
                    if (j > 0 && num[j] == num[j - 1] && !alreadyUsed[j - 1]) continue;
                    alreadyUsed[j] = true;
                    ans[i] = num[j];
                    dfs(i + 1, n, results, num);
                    alreadyUsed[j] = false;
                }
            }
        }
        vector< vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(), num.end());  // Key to remove duplicate: Sorting!!!
            int n = num.size();
            ans.resize(n);
            alreadyUsed.resize(n);
            fill(alreadyUsed.begin(), alreadyUsed.end(), false);
            vector<vector<int> > *results = new vector<vector<int>>();
            if (n <= 0) return *results;
            dfs(0, n, results, num);
            return *results;
        }
};

Compared with the other two methods, the pros and cons are as follows:

  • pros: easier to come up with and to understand following the standard backtracking (DFS) framework
  • cons: do not have the sense of in-place operation and it is not straightforward to convert it into non-recursive implementation

(2) Using Swap and Generate Permutation in place (Recursive Implementation)

  • Key Idea: To understand this method, the key fact we need to know and keep in mind is that for each number A[i] by swapping A[i] and A[j] where j >= i, it generates a unique new permutation (assume there is no duplicates in the input for now). For example, here is how to generate all the unique permutations for [1, 2, 3]: for the A[i], swap A[i] and A[j] where j = 0, 1, 2 to generate [1, 2, 3], [2, 1, 3] and [3, 1, 2], for A[1] of each of the three permutations, we swap A[1] and A[2], each of them generates a new permutation [1, 2, 3] -> [1, 3, 2]; [2, 1, 3]-> [2, 3, 1]; [3, 1, 2]->[3, 2, 1] now we have all the 6 permutations. To understand why it works, think about this, during 0-iteration, all numbers A[0…m] could be in the 0 position, and for each of the these A[0…m], permutation,  recursively, the later numbers A[1…m] could be in A[1], essentially, this agrees with the recursive definition of permutation.
  • Remove Duplicate: The tricky thing is that, to avoid duplicates, when we do swapping between num[k] and num[i], we need to make sure in the interval [k, i), there is no number with the same value as of num[i]. This could be explained by thinking about three key points(1) to avoid duplicated permutation, we just need to avoid permute the same numbers; (2) suppose there is a duplicated number of num[i] in [k, i), then sometime in the future after we have done the swapping(num[k], num[i]), we will also swap this duplicated number with num[i], that is, we are essentially swapping the same numbers. (3) it is not enough to check just num[k] and num[i] whether they are the same number when swapping them because of (2), and (2) also includes the case that we check num[k] and num[i] are same or not. Combine (1) , (2) and (3), we make sure we don’t swap the same numbers and thus avoiding all the duplicated permutations. 

The following C++ source code is accepted by LeetCode OJ to pass both Permutation I and II problems:

class Solution {
public:
bool sameExist(const vector<int> &num, int k, int j) {
    bool flag = false;
    for (int i = k; i < j && !flag; ++i) if (num[i] == num[j]) flag = true;
    return flag;
}
void permuteInner(vector<int> &num, int pos, int m, vector<vector<int>> *results) {
if (pos == m) { results->push_back(num); return ; }
    for (int j = pos; j <= m; ++j) {
        if (sameExist(num, pos, j)) continue;
        swap(num[pos], num[j]);
        permuteInner(num, pos + 1, m, results);
        swap(num[pos], num[j]);
    }
}
vector<vector<int> > permuteUnique(vector<int> &num) {
    vector<vector<int> > *results = new vector<vector<int>>();
    int n = num.size();
    if (n < 2) { results->push_back(num); return *results; }
    permuteInner(num, 0, n - 1, results);
    return *results; // clean up
}
};

Compared with the other two methods, the pros and cons are as follows:

  • pros: in-place swap, do not need additional information to test if a number is already used or not
  • cons: difficult to come up with the swapping idea, not easy to understand it if never seen this before, the linear scan sameExist() check is less efficient than the one time global sorting to remove duplicates as in (1)

(3) Using Swap and Generate Permutation in place (Non-Recursive Implementation)

Well, this is actually the non-recursive implementation of the ideas in (2) and sorting is combined to remove duplicates rather than linear scanning through [k, i) to check whether there is duplicates of num[i] as in (2). Well, combining sorting here is not encouraging because each time we need to sort the remaining part of the permutation, so this is actually no better (actually cost more than the linear scan in (2)) than the directly approach to check. The sorting in (1) cannot directly be combined into (2) (that is, only a global sorting for once) because after swapping, the order of the remaining part is disturbed anyways thus making the global sorting useless and we essentially need to sort it again and again as follows. So the following C++ source code is accepted by LeetCode OJ to pass both Permutation I and II problems:

class Solution {
public:
 vector<vector<int> > permuteUnique(vector<int> &num) {
    vector<vector<int>> results;
    results.push_back(num);
    int n = num.size();
    if (n < 2) return results;
    int pos = 0;
    while (pos < n) {
        for (int i = results.size() - 1; i >= 0; --i) {
            sort(results[i].begin() + pos, results[i].end());
            for (int j = pos + 1; j < n; ++j) {
                if (results[i][j] == results[i][j - 1]) continue;
                swap(results[i][pos], results[i][j]);
                results.push_back(results[i]);
                swap(results[i][pos], results[i][j]);
            }
        }
        ++pos;
    }
    return results;
}
};

Compared with the other two methods, the pros and cons are as follows:

  • pros: non-recursive implementation is more efficient than (1) and (2), in-place swapping, no need additional array except the results to keep all the permutations
  • cons: need to sort the remaining portion of the permutation everytime, less efficient than (1) and (2) in this sense. Try to utilize the advantage of the global sorting trick, but fails and actually leads more cost than the linear check in (2)

References

http://blog.csdn.net/morewindows/article/details/7370155

http://fisherlei.blogspot.ca/2012/12/leetcode-permutations-ii.html.

Additional Reference:

Update on April 27, 2013. There is another (systematic) way to remove the duplicates as in another post “leetcode: Subsets I and II“: if two adjacent numbers say A and B are equal, then only when A is used, B could be used in that subset.

Summary

3 methods including DFS, Iterative Swap, Recursive Swap are given (pros and cons) to solve LeetCode Permutations problem and use sorting to remove duplicates.

Written on April 17, 2013