全配列c++実装
9507 ワード
#include <iostream>
#include <vector>
#define arr_size(A) (sizeof(A)/sizeof(A[0]))
using namespace std;
template<typename Type>
vector<Type>& permutation(vector<Type> des, vector<Type> src)
{
static vector<Type> result;
if( src.empty() ){
//append a permutation to result-vector
result.insert(result.end(), des.begin(), des.end());
return result;
}
Type curr=src.back();
src.pop_back();
for(typename vector<Type>::iterator it=des.begin();it<des.end()+1; it++){
//try to insert an item to any possible position
it=des.insert(it,curr);
permutation(des,src);
//remove it for next insertion
des.erase(it);
}
return result;
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10};
vector<int>vi(arr,arr+arr_size(arr));
vector<int>result=permutation(vector<int>(),vi);
// print results to stdout
for(vector<int>::iterator it=result.begin(); it<result.end();){
for(int i=0; i<arr_size(arr); i++){
cout<<*it<<" ";
it++;
}
cout<<endl;
}
cout<<"permutations count: "<<result.size()/arr_size(arr)<<endl;
}