非遞歸的全排列輸出

對于任意給定的1~9, 給出所有的不出現重複數字的排列

由于讨厭使用遞歸（代碼好寫，但是執行效率不高），也不想使用stl模闆之類，于是用标準c++單獨寫了一個代碼

如下：

//

// 本代碼用于生成n的全排列，結果儲存在permutation二維數組當中

// 生成的原理：

//     假定一個完成了n-1個數的不重複的排列，并放到permuatation數組當中的前(n-1)！行

//     那麼第n個數字進來，隻是在原有的排列當中的n個位置插入

//     是以，隻要把原有的(n-1)！個組合複制n次，每次在不同的位置插入n這個數字即可

// 為了友善使用

//     這個實作放到函數當中，傳回到數組作為參數傳遞進來使用

#include <iostream>

#include <cstring>

using namespace std;

unsigned char* permutation(int len)

{

    long int SIZE=1;

    for (int i=2; i<=len; i++) SIZE*=i;

    unsigned char *permutation= new unsigned char [SIZE*len];

    long int nCount = 1;  // 用于記錄(n-1)!這個數字, 是排列好的所有的序列數量

    permutation[len-1]=1;  // 初始化

    // 把n=2到len依次填充到數組裡面

    for ( int n=2; n<=len; n++) {

        // 把已經排好序的nCount=(n-1)!個序列，再複制n-1組，以備插值

        for (int i=1; i<n; i++) {

            memcpy(&permutation[nCount*i*len], &permutation[0], nCount*len);

        };

        unsigned char * pTemp = &permutation[0];

        for ( int i=0; i<n; i++ ){

            // 把複制出來的n-1組，以及原有的1組，共n組排列插入新數字n

            for (int j=0; j<nCount; j++) {

                unsigned char * p; 

                p = pTemp+len-n;

                for ( int k=0; k<n-1-i; k++, p++) {

                    *p = *(p+1);

                };

                *p = n; 

                pTemp+=len;

            };

        }

        nCount *=n;

    };

    return permutation;

}

int main(int argc, const char * argv[]) {

    cout << "Starting......";

    int len = 9;

    unsigned char * p = permutation(len);

    cout << endl;

    cout << "Head 20:"<<endl;

    for ( int i=0; i<20; i++) {

        for (int j=0; j<len; j++) {

            cout << (int)p[i*len+j];

        };  cout << endl;

    }; cout << endl;

    int totalNumber=1;

    for (int i=2; i<=len; i++) totalNumber*=i;

    cout << "Tail 20:"<<endl;

    for (int i=totalNumber-20; i<totalNumber;i++) {

        for ( int j=0; j<len; j++) {

            cout << (int) p[i*len+j];

        };  cout << endl;

    }; cout << endl;

    delete p;

    return 0;

}

// 說明儲存結果是放到一維數組當中，每個數占據一個BYTE也就是unsigned char類型

// 數組的長度是 len * len！ * sizeof(unsigned char)

// len參數是9的時候，傳回到一維數組的大小就是9*9! = 9*362 880 大約36MB

// 如果是10！  那就再擴大百倍，3.6GB    嘿嘿