实现数组全排列

今天做笔试的时候忘了全排列怎么写。依稀记得有个next_permutation()。

1. 后来自己用递归实现了一下数组的全排列。 

#include <iostream>
#include <vector>
using namespace std;
//array是初始数组，result是存储全部排列的结果
void fullArray(vector<int> array, vector<vector<int> > &result )
{    
    if(array.size() == 1) {
        result.push_back( array);
    }
    vector<int> temp0;
    if(array.size() == 2) {
        result.push_back(array);    
        temp0.push_back(array[1]);
        temp0.push_back(array[0]);
        result.push_back(temp0);
    } else {
        for(int i = 0; i < array.size(); i++) 
        {    
        /*vector<int> temp;
        temp.push_back(array[i]);
        */
            int temp = array[i];

            vector<int> temp2 = array;
            temp2.erase(temp2.begin()+i);
            vector<vector<int> >rest;
            fullArray(temp2, rest );
            for(int i = 0; i < rest.size(); i++) 
            {
                vector<int> arr;
                arr.push_back(temp);
                arr.insert(arr.end(), rest[i].begin(), rest[i].end());
                result.push_back(arr);
            }
        }
    }

}
int main()
{    
    vector<int> array;
    for(int i=0; i < 3; i++)
    {
        array.push_back(i);
    }
    vector<vector<int> > result;
    fullArray(array, result);
    cout << "number:" << result.size() << endl;
    for(int i = 0; i < result.size(); i++)
    {
        for(int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << "," ;
        }
        cout << endl;
    }
    return 0;
}
//output: 
/*number:6
*0,1,2,
*0,2,1,
*1,0,2,
*1,2,0,
*2,0,1,
*2,1,0,
*/

2.  以及调用next_permuation()函数，在algorithm函数中，刷题还是太少(- _-D)。 

int main()
{
    vector<int> array;
    for(int i = 0; i < 3; i++)
    {
        array.push_back(i);
    }

    do {
        for(auto e : array)
        {
            cout << e << ",";
        }
        cout << endl;
    } while(next_permutation(array.begin(), array.end()));

}

//output: 
/*
0,1,2,
0,2,1,
1,0,2,
1,2,0,
2,0,1,
2,1,0,
*/

 3. 使用深度优先

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > result;
        //for(int i = 0; i < nums.size)
        //vector<int> temp;
        //temp.pus_back()
        vector<bool> used;
        used.resize(nums.size());
        for(int i = 0; i < nums.size(); i++) {
            used[i] = false;
        }
        vector<int> pre;
        dfs(nums, 0, result, pre, used);        
        return result;
        
        
    }
    
    void dfs(vector<int> & nums, int index, vector<vector<int>> &re, vector<int> &pre, vector<bool> &used)
    {
        
        if(index == nums.size()) {
            vector<int> temp;
            temp.insert(temp.begin(), pre.begin(), pre.end());
            re.push_back(temp);
        }
                
        for(int i = 0; i < nums.size(); i++)
        {
            if(!used[i]){
                used[i] = true;
                pre.push_back(nums[i]);
                dfs(nums, index+1, re, pre, used);
                used[i] = false;
                pre.erase(pre.end()-1);
                //pre.pop_back();
                
            }            
        }     
        
    }
    
};