Permutation | leetcode/lintcode题解/算法学习笔记

雪柳花明 2016-10-25

展开全文

Permutation - 排列

排列常见的有数字全排列，字符串排列等。

Permutations - 全排列

Source

lintcode: (15) Permutations

Given a list of numbers, return all possible permutations.

Example
For nums [1,2,3], the permutaions are:

[

    [1,2,3],

    [1,3,2],

    [2,1,3],

    [2,3,1],

    [3,1,2],

    [3,2,1]

]

Challenge
Do it without recursion

题解

使用之前subsets的模板，但是在取结果时只能取list.size() == nums.size()的解，且在添加list元素的时候需要注意除重。

C++

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector > permute(vector nums) {
        vector > result;
        if (nums.empty()) {
            return result;
        }

        vector list;
        backTrack(result, list, nums);

        return result;
    }

private:
    void backTrack(vector > &result, vector &list,                    vector &nums) {
        if (list.size() == nums.size()) {
            result.push_back(list);
            return;
        }

        for (int i = 0; i != nums.size(); ++i) {
            // remove the element belongs to list
            if (find(list.begin(), list.end(), nums[i]) != list.end()) {
                continue;
            }
            list.push_back(nums[i]);
            backTrack(result, list, nums);
            list.pop_back();
        }
    }
};

源码分析

在除重时使用了标准库find(不可使用时间复杂度更低的binary_search，因为list中元素不一定有序)，时间复杂度为 O(N), 也可使用hashmap记录nums中每个元素是否被添加到list中，这样一来空间复杂度为 O(N), 查找的时间复杂度为 O(1).

在list.size() == nums.size()时，已经找到需要的解，及时return避免后面不必要的for循环调用开销。

使用回溯法解题的关键在于如何确定正确解及排除不符条件的解(剪枝)。

Unique Permutations

Source

lintcode: (16) Unique Permutations

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example
For numbers [1,2,2] the unique permutations are:

[

    [1,2,2],

    [2,1,2],

    [2,2,1]

]

Challenge
Do it without recursion.

题解

在上题的基础上进行剪枝，剪枝的过程和 Subsets | Algorithm 中的 Unique Subsets 一题极为相似。为了便于分析，我们可以先分析简单的例子，以 [1,2?1??,2?2??] 为例。按照上题 Permutations 的解法，我们可以得到如下全排列。

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

从以上结果我们注意到1和2重复，5和3重复，6和4重复，从重复的解我们可以发现其共同特征均是第二个 2?2?? 在前，而第一个 2?1?? 在后，因此我们的剪枝方法为：对于有相同的元素来说，我们只取不重复的一次。嗯，这样说还是有点模糊，下面以 [1,2?1??,2?2??] 和 [1,2?2??,2?1??] 进行说明。

首先可以确定 [1,2?1??,2?2??] 是我们要的一个解，此时list为 [1,2?1??,2?2??], 经过两次list.pop_back()之后，list为 [1], 如果不进行剪枝，那么接下来要加入list的将为 2?2??, 那么我们剪枝要做的就是避免将 2?2?? 加入到list中，如何才能做到这一点呢？我们仍然从上述例子出发进行分析，在第一次加入 2?2?? 时，相对应的visited[1]为true(对应 2?1??)，而在第二次加入 2?2?? 时，相对应的visited[1]为false，因为在list为 [1,2?1??] 时，执行list.pop_back()后即置为false。

一句话总结即为：在遇到当前元素和前一个元素相等时，如果前一个元素visited[i - 1] == false, 那么我们就跳过当前元素并进入下一次循环，这就是剪枝的关键所在。另一点需要特别注意的是这种剪枝的方法能使用的前提是提供的nums是有序数组，否则无效。

C++

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector > permuteUnique(vector &nums) {
        vector > ret;
        if (nums.empty()) {
            return ret;
        }

        // important! sort before call `backTrack`
        sort(nums.begin(), nums.end());
        vector visited(nums.size(), false);
        vector list;
        backTrack(ret, list, visited, nums);

        return ret;
    }

private:
    void backTrack(vector > &result, vector &list,                    vector &visited, vector &nums) {
        if (list.size() == nums.size()) {
            result.push_back(list);
            // avoid unnecessary call for `for loop`, but not essential
            return;
        }

        for (int i = 0; i != nums.size(); ++i) {
            if (visited[i] || (i != 0 && nums[i] == nums[i - 1]                 && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            list.push_back(nums[i]);
            backTrack(result, list, visited, nums);
            list.pop_back();
            visited[i] = false;
        }
    }
};