配列組合せC++実装

最近一つの試験を準備して、組み合わせを試験する内容があることを発見したので、この問題を研究します.まず配列の問題を検討する.
 
例えば1,2,3,4の配列を求める

 Int a[]={1,2,3,4} 

1つ目の方法:

void ArrangementS(int *a)
{
 int count=0;

 for(int i=0;i<4;++i)

 for(int j=0;j<4;++j)

 for(int k=0;k<4;++k)

 for (int s=0;s<4;++s)

 if(i!=j && i!=k && i!=s && j!=k && j!=s && k!=s)

 {

  cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<a[s]<<" "<<endl;

  count++;

  }

 

 cout<<count<<endl;

}

この方法は効率が悪いので,輪替え法を用いた第2の方法が生まれた.
 
2つ目の方法:

void method2(int *a)

{

        

        int count=0;

        for(int k=0;k<4;k++)

        {

                  if(k！=0)

                  {

                           swap(a[0],a[k]);

                  }

                  for(int j=1;j<4;j++)

                  {

                           if(j!=1)

                           {

                                    swap(a[1],a[j]);

                           }

                           for(int s=2;s<4;s++)

                           {

                                    if(s!=2)

                                    {

                                              swap(a[2],a[s]);

                                    }

 

                        std::cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<endl;
                                    count++;
                                    if(s!=2)

                                    {
                                              swap(a[2],a[s]);
                                    }

                           } 

                           if(j!=1)

                           {
                                  swap(a[1],a[j]);

                           }
                  }

                           if(k!=0)
                  {
                           swap(a[0],a[k]);

                  }
        }

                   std::cout<<count<<endl;

}

 
しかし1,2,…,Nを求めるときには第2の方法が求めにくいので,第2の方法(再帰)を書き換える.
3つ目の方法:

void arrangement(int *a,int start,int end)

{
             if(start==end)
                {

                           for(int i=0;i<N;++i)

                           std::cout<<a[i]<<" ";

                           std::cout<<endl;

                         

                      return;

                  }

          for(int i=start;i<=end;++i)

        {
                  if(i!=start)                  
                     swap(a[start],a[i]);                 
                  arrangement(a,start+1,end);
                  if(i!=start)
                     swap(a[start],a[i]);

        }
}

 
組合せ問題の比較的簡単な実現関数は以下の通りである.

void Portfolio(int *a,int start,int end,int nselN)

{
        static int nselTemp=nselN;
        static std::vector<int> selArray(nselN);
         if(nselN==0)

             {
                        
                     for(int i=0;i<nselTemp;++i)
                     cout<<a[selArray[nselTemp-i-1]]<<" ";
                     cout<<endl;
                     return;
             }

           for(int i=start;i<=end-nselN+1;++i)

        {

                  selArray[nselN-1]=i;
                  Portfolio(a,i+1,end,nselN-1);

        }

}