[leetcode]permutations配列
8444 ワード
2つ書きました.1つは直接的な再帰的な実装です.
もう1つはSTLのようなnext_でpermutation関数メソッドの実装:
次のリンクはSTLのnext_ですpermutation関数の説明:
http://www.cnblogs.com/Azhu/articles/3897586.html
辞書の左から小到着順で現在のシーケンスの次のソートが与えられます.シーケンスに重複要素がある場合に適用されます.関数のプロセスは次のとおりです.
1.右から隣接する2つの数を探し、next2.nextより大きい最初の数を右から探し、midと記す
3.mextとmidを交換する
4.逆順next 1(next 1を含む)から右端まで
main関数:
class Solution {
public:
void swap(vector<int> &num,int left,int right)
{
num[left] = num[left]^num[right];
num[right] = num[left]^num[right];
num[left] = num[left]^num[right];
}
void permuteHelp(vector<int> &num,int fix,vector< vector<int> > &result)
{
if(fix==num.size()-1)
{
result.push_back(num);
return;
}
permuteHelp(num,fix+1,result);
for(int i=fix+1;i<num.size();i++)
{
swap(num,i,fix);
permuteHelp(num,fix+1,result);
swap(num,i,fix);
}
}
vector<vector<int> > permute(vector<int> &num) {
vector< vector<int> > result;
if (num.size()<1)
return result;
if(num.size()<2)
result.push_back(num);
else
permuteHelp(num,0,result);
return result;
}
};もう1つはSTLのようなnext_でpermutation関数メソッドの実装:
次のリンクはSTLのnext_ですpermutation関数の説明:
http://www.cnblogs.com/Azhu/articles/3897586.html
辞書の左から小到着順で現在のシーケンスの次のソートが与えられます.シーケンスに重複要素がある場合に適用されます.関数のプロセスは次のとおりです.
1.右から隣接する2つの数を探し、next
3.mextとmidを交換する
4.逆順next 1(next 1を含む)から右端まで
class Solution{
public:
int factorial(int n)
{
return n<2?1:factorial(n-1)*n;
}
void next_per(vector<int> & num)
{
vector<int>::iterator first,last,next,next1,mid;
first = num.begin();
last = num.end();
next = last;
if(first==--next||first==last)
return ;
while(1)
{
next1=next--;
if(*next<*next1)
{
mid = last;
while(!(*next<*--mid));
iter_swap(next,mid);
reverse(next1,last);
return ;
}
if(next==first)
{
reverse(first,last);
return ;
}
}
}
vector< vector<int> > permute(vector<int> &num)
{
vector< vector<int> > result;
if(num.size()<1)
return result;
sort(num.begin(),num.end());
result.push_back(num);
for(int i=1;i<factorial(num.size());i++)
{
next_per(num);
result.push_back(num);
}
return result;
}
};main関数:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
vector<int> num;
int a = 2;
for(int i=0;i<a;i++)
num.push_back(i);
Solution solution;
vector< vector<int> > result;
result = solution.permute(num);
for(int id = 0;id<result.size();id++)
{
for(int i=0;i<a;i++)
cout<<result[id][i]<<' ';
cout<<endl;
}
cout<<result.size()<<endl;
return 0;
}