1 template <typename T>
 2 inline void swap(T* array, unsigned int i, unsigned int j)
 3 {
 4     T t = array[i];
 5     array[i] = array[j];
 6     array[j] = t;
 7 }
 8 
 9 /*
10  * 递归输出序列的全排列
11  */
12 void FullArray(char* array, size_t array_size, unsigned int index)
13 {
14     if(index >= array_size)
15     {
16         for(unsigned int i = 0; i < array_size; ++i)
17         {
18             cout << array[i] << ‘ ‘;
19         }
20 
21         cout << ‘\n‘;
22 
23         return;
24     }
25 
26     for(unsigned int i = index; i < array_size; ++i)
27     {
28         swap(array, i, index);
29 
30         FullArray1(array, array_size, index + 1);
31 
32         swap(array, i, index);
33     }
34 }

/*
 * 将数组中的元素翻转
 */
inline void Reverse(unsigned int* array, size_t array_size)
{
    for(unsigned i = 0; 2 * i < array_size - 1; ++i)
    {
        unsigned int t = array[i];
        array[i] = array[array_size - 1 - i];
        array[array_size - 1 - i] = t;
    }
}

inline int LexiNext(unsigned int* lexinum, size_t array_size)
{
    unsigned int i, j, k, t;

    i = array_size - 2;

    while(i != UINT_MAX && lexinum[i] > lexinum[i + 1])
    {
        --i;
    }

    //达到字典序最大值
    if(i == UINT_MAX)
    {
        return 1;
    }

    for(j = array_size - 1, k = UINT_MAX; j > i; --j)
    {
        if(lexinum[j] > lexinum[i])
        {
            if(k == UINT_MAX)
            {
                k = j;
            }
            else
            {
                if(lexinum[j] < lexinum[k])
                {
                    k = j;
                }
            }
        }
    }

    t = lexinum[i];
    lexinum[i] = lexinum[k];
    lexinum[k] = t;

    Reverse(lexinum + i + 1, array_size - i - 1);
    return 0;
}

/*
 * 根据字典序输出排列
 */
inline void ArrayPrint(const char* array, size_t array_size, const unsigned int* lexinum)
{
    for(unsigned int i = 0; i < array_size; ++i)
    {
        cout << array[lexinum[i]] << ‘ ‘;
    }

    cout << ‘\n‘;
}

/*
 * 基于逆序数的全排列输出
 */
void FullArray(char* array, size_t array_size)
{
    unsigned int lexinumber[array_size];

    for(unsigned int i = 0; i < array_size; ++i)
    {
        lexinumber[i] = i;
    }

    ArrayPrint(array, array_size, lexinumber);

    while(!LexiNext(lexinumber, array_size))
    {
        ArrayPrint(array, array_size, lexinumber);
    }
}