非递归的全排列输出

对于任意给定的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    嘿嘿