コンビネーション数印刷

コンビネーション数印刷
/[北京直真笔问题]例えば4つの数を与えて、それぞれ1,2,3,4です.その中から3つの組み合わせ数を選択する必要があり、繰り返すことはできません.
印刷:123124234....
方法1:【考え方】1)1,2,3,4を配列に格納し、4つの数から1つの数、すなわちselValを選択する.2)次の作業は残りの3つの数の中から2つの数を選択し、selVal以外の残りの3つの数を記憶する必要がある.3)選択してselValと選択した2つの数を印刷すればよい.
【解析】:時間的複雑度O(n 3),空間的複雑度O(n).

const int g_nCnt = 4;
int g_nArr[g_nCnt] ={1,2,3,4};
// 3    2       .
void selTwoFromThree(intnArray[], int nSize, int nAlreadySel)
{
for(int i = 0; i < nSize; i++)
   {
           for(int j = i+1; j < nSize; j++)
           {
                    cout << nAlreadySel << "\t"<< nArray[i] << "\t" << nArray[j] << endl; // i j
                    cout << nAlreadySel << "\t"<< nArray[j] << "\t" << nArray[i] << endl; // j i
           }
  }
}
 
void printArray(intnArray[], int nSize)
{
int nAleardySel = 0;
for(int i = 0; i < nSize; i++)
{
           int *pArrAdd = new int[3];
           int k = 0;
           nAleardySel = nArray[i];
           for(int j = 0; j < nSize; j++)
           {
                    if(nArray[j] != nAleardySel)
                    {
                             pArrAdd[k++] = nArray[j];
                    }//end if
           }//end for j
          
           selTwoFromThree(pArrAdd,g_nCnt-1,nAleardySel);
           cout << endl;
}//end fori
}

方法2:【考え方】4つの数の中から選択した3つの数を百桁と見なすため、印刷の過程となり、4つの数の中から3つの数を選んだ全配列4*4*4=64の中から100桁、10桁、個位が重複しない4*3*2=24個の数を選択する過程となる.
【解析】:時間的複雑度O(n 3),空間的複雑度O(1).余分なスペースは必要ありません.

#define MAXN 4
void combineSelPrint(intmaxCnt)
{
static int count = 0;
for(int i=1;i<=MAXN;i++)//     
{
           for(int j=1;j<=MAXN;j++)//     
           {
                    if(j != i)
                    {
                             for(int k=1;k<=MAXN;k++)//     
                             {
                                       if(k != j && k != i)
                                       {
                                                printf("%d,%d,%d
",i,j,k);
                                                ++count;
                                       }
                             }//end for k
                    }//end if j
           }//end for j
}//end for i
cout << "--------------count = " << count<< "-------------" << endl;
}
 
 
int main()
{
combineSelPrint(MAXN);
return 0;
}

【考える?】:時間の複雑さの低いアルゴリズムはありますか?あるいは再帰的に実現する良い方法ですか?
【方法3】:コンビネーション印刷を再帰的に実現し、C(n,m)、n個の数の中からm個(m<=n)個の全てのコンビネーション印刷を選択する.
全配列を印刷する方法について議論する文章はたくさんありますが、結局は多くの問題を巡る基礎ですね.ここでは、コンビネーション数を印刷する方法について説明します.まず、一例を見てみましょう.C(5,3)=10 1 2 3 1 2 4 1 2 5 1 3 4 1 3 3 5 1 4 5 5 2 3 4 4 4 4 5みんなは気づいていません.1|2 3 1|2 4 1|2 4 1|2 5 1|3 4 1|3 5 1|4 4 4 4 1|3 5------C(4,2)‰は{2,3,4,5}の中から2つを選ぶことができます.2|3 4 2|3 5 2|4 5------C(3,2)⊃は{3,4,5}の中から2つを選ぶことができます.3|4 5------C(2,2)⑤{4,5}の中から2つだけ選べる.
 
これで再帰アルゴリズムが簡単に書けます.Algorithm combination(n, k, A[l..n+l-1]) 1. if k = 0 2. print ary[1..k] 3. else 4. for i←1 to n-k+1 5. ary[index++] = A[l+i-1] 6. combination(n-i,k-1, A[l+i..n+l-1]) 7. --index 8. endforみんなはどうしてindexを出すのか疑問に思うかもしれませんが、あと少し減らします(手作業で計算すればわかります).
 
【実装部】

int *dst_array,top=0;//    ，        ，count         
int cnt = 0;
 
//     n     
static void printA(int*parray,int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d ",parray[i]);
    }
}
 
//       
static  void print_combine(int *pArray,int n,int m)
{
    if(n < m || m==0)  
    {
           return ;//   ：     ，  
    }
 
    print_combine(pArray+1,n-1,m);//   ：             
 
    dst_array[top++]=pArray[0];//   ：      
    if(m==1)
     {  //   -1：       
        printA(dst_array,top);
        printf("
");
        cnt++;
        top--;
        return;
    }
 
    print_combine(pArray+1,n-1,m-1);//   -2：           
    top--;//     top 
}
 
int main()
{
    int n,m,*parray;//       ， n m
    printf("---     n     m        (n   1,2,3....n---
");
    printf("---   n  m 
---");
    scanf("%d%d",&n,&m);
 
    printf("
---       ---
");
    parray=(int *)malloc(sizeof(int)*n);
    dst_array=(int *)malloc(sizeof(int)*m);
 
    int i;
    for(i=0;i<n;i++)
    {
           //     
        //scanf("%d",&parray[i]);
           parray[i] = i+1;
    }
    print_combine(parray,n,m);//          
 
    printf("=====C（%d，%d）  ：%d =====",n,m,cnt);
 
    free(parray);
    free(dst_array);
    return 0;
}

       
方法3の参考:http://bbs.pfan.cn/post-270256.html
     http://blog.csdn.net/challenge_c_plusplus/article/details/6641950
筆者は方法3をデバッグして、使いやすいです.しかし、筆者はその中の再帰的な部分の原理について理解できず、疑問を持っているので、紹介してください.