輸出數組全排列

• 字元串的排列組合問題：http://blog.csdn.net/wuzhekai1985/article/details/6643127
• 輸出全排列(遞歸&非遞歸)
• http://blog.csdn.net/hackbuteer1/article/details/7462447
• 從數組中取出n個元素的所有組合（遞歸實作）
• 之前一直沒有實作過，今天了解一下

#include <iostream>
#include <iterator>  
using namespace std;


//輸出數組全排列

//算法思路：
//(1)n個元素的全排列 = （n - 1個元素的全排列） + （另一個元素作為字首）；
//(2)出口：如果隻有一個元素的全排列，則說明已經排完，則輸出數組；
//(3)不斷将每個元素放作第一個元素，然後将這個元素作為字首，并将其餘元素繼續全排列，等到出口，出口出去後還需要還原數組；

void perm(int list[], int k, int m)
{
    if (k == m)
    {
        copy(list, list + m, ostream_iterator<int>(cout, " "));
        cout << endl;
        return;
    }
    for (int i = k; i < m; i++)//第一次自己和自己換  
    {
        swap(list[k], list[i]);
        perm(list, k + 1, m);
        swap(list[k], list[i]);
    }
}

int main()
{
    int List[] = { 1, 2, 3 };
    perm(List, 0, sizeof(List) / sizeof(int));
    return 0;
}      

 - 參考

1.全排列：用遞歸的思想求出全排列
#include "stdafx.h"
#include <iostream>
using namespace std;
 void swap(int &a,int &b)//交換連個元素
 {
     int tem;
     tem = a;
     a = b;
     b = tem;
 }
 void cal(int *a,int first,int length)
 {
     if(first == length)//如果遞歸到深層時，到最後交換的元素即時最後一個元素時就列印出來
     {
         for(int i = 0; i <= length; i++)
         cout<<a[i]<<" ";
         cout<<endl;
     }
     else
     {
         for(int i = first; i <= length; i++)
         {//循環周遊使得目前位置後邊的每一個元素都和目前深度的第一個元素交換一次
             swap(a[first],a[i]);//使得與第一個元素交換
             cal(a,first+1,length);//深入遞歸，此時已确定前邊的元素，處理後邊子序列的全排列形式。
             swap(a[first],a[i]);//恢複交換之前的狀态
         }
     }
 }
 int main()
 {
     int a[6] = {1,2,3,4,5,6};
     cal(a,0,5);
     return 0;
 }

2.借助于上面的求出全排列的方法，求組合的時候隻是在遞歸到低時輸出的不一樣，這裡隻輸出組合個數的元素：
#include "stdafx.h"
#include <iostream>
using namespace std;
 void swap(int &a,int &b)//交換連個元素
 {
     int tem;
     tem = a;
     a = b;
     b = tem;
 }
 void cal(int *a,int first,int length,int r)
 {
     if(first == length)//如果遞歸到深層時，到最後交換的元素即時最後一個元素時就列印出來
     {
         for(int i = 0; i <= r; i++)
         cout<<a[i]<<" ";  //bug 錯誤的：如果12345；則n(5,2):(12345,12435,12354...等輸出前面的都是一樣的)
         cout<<endl;
     }
     else
     {
         for(int i = first; i <= length; i++)
         {//循環周遊使得目前位置後邊的每一個元素都和目前深度的第一個元素交換一次
             swap(a[first],a[i]);//使得與第一個元素交換
             cal(a,first+1,length,r);//深入遞歸，此時已确定前邊的元素，處理後邊子序列的全排列形式。
             swap(a[first],a[i]);//恢複交換之前的狀态
         }
     }
 }
 int main()
 {
     int a[6] = {1,2,3};
     cal(a,0,2,1);
     return 0;
 }      

C/C++基本文法學習

STL

C++ primer