全配列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<Typedesvector<Typesrc)
{
    static 
vector<Typeresult;
    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()+1it++){
        
//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=0i<arr_size(arr); i++){
            
cout<<*it<<" ";
            
it++;
        }
        
cout<<endl;
    }
    
cout<<"permutations count: "<<result.size()/arr_size(arr)<<endl;