Leetcode: Permutations-蒲公英云

Leetcode: Permutations

题目：
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].

思路分析：
思路一：
最容易想到的就是递归了！每次在num中拿出1个数字放在第一个，然后剩下的数字做一个全排列。
C++参考代码：

class Solution
{
public:
    vector<vector<int> > permute(vector<int> &num)
    {
        int size = int(num.size());
        vector<vector<int>> result;//num全排列的结果
        if (1 == size)
        {
            result.push_back(num);
            return result;
        }
        vector<int> currentElement;//临时保存当前的num
        vector<vector<int>> remainingResult;//num除去一个元素以后剩下元素的全排列结果
        vector<int> currentResult;//保存当前num的每个全排列
        for (int i = 0; i < size; ++i)
        {
            currentElement = num;
            currentElement.erase(currentElement.begin() + i);//去掉第i个元素（从0开始）
            remainingResult = permute(currentElement);//后续元素的全排列
            int remainingResultSize = int(remainingResult.size());
            for (int j = 0; j < remainingResultSize; ++j)
            {
                currentResult = remainingResult[j];
                currentResult.insert(currentResult.begin(), num[i]);//在开始位置插入num[i]
                result.push_back(currentResult);
            }
        }
        return result;
    }
};

思路二：
同样使用递归：每次循环交换第一个元素和后面元素的位置，然后第一个元素和后面元素的全排列依次加入结果数组中。比如：

对于数组[1,2,3]

交换1和1的位置（其实第一次不用交换），生成[2, 3]的全排列[2, 3]和[3, 2]，然后把1加上去生成[1, 2, 3]和[1, 3, 2]。交换完以后换回来。
交换1和2的位置，生成[1, 3]的全排列[1, 3]和[3, 1]，然后把2加上去生成[2, 1, 3]和[2, 3, 1]。交换完以后换回来。
交换1和3的位置，生成[2, 1]的全排列[2, 1]和[1, 2]，然后把3加上去生成[3, 2, 1]和[3, 1, 2]。交换完以后换回来

其实思路一和思路一有相似之处：都是选出一个元素，剩余元素做全排列。不同的是一：循环遍历给定数组进行计算；二通过交换第一个元素和后面元素的位置，结果为第一个元素+后面元素的全排列。
C++参考代码：

class Solution {
private:
    vector<vector<int>> result;
    int size;
    void permuate(vector<int> &num, int index)
    {
        if (index == size)
        {
            result.push_back(num);
            return;
        }
        for (int i = index; i < size; ++i)
        {
            swap(num[index], num[i]);//交换i和index元素
            permuate(num, index + 1);//计算除去index元素，后面元素的全排列
            swap(num[index], num[i]);//再换回来
        }
    }
public:
    vector<vector<int> > permute(vector<int> &num)
    {
        size = int(num.size());
        permuate(num, 0);
        return result;
    }
};

思路三：
使用STL提供的next_permutation函数，next_permutation函数能够以字典序列的方式输出排列的结果，详见：next_permutation。不过直接调用库函数貌似没有体现自己的思考与自己的算法！
C++参考代码：

class Solution
{
public:
    vector<vector<int> > permute(vector<int> &num)
    {  
        vector<vector<int> > result;
        sort(num.begin(), num.end());//给num升序排序
        result.push_back(num);
        while (next_permutation(num.begin(), num.end()))
        {
            result.push_back(num);
        }
        return result; 
    }  
};