Contents

1. 1. C++中全排列函数实现原理

C++中全排列函数实现原理

//补:N个元素（不同的）的全排列总数为n！个
//如果有相同的元素就把那个元素个数的阶乘给除掉，具体看hdu5651

#include <cstdio>

template <typename T>
void swap(T& a, T& b){

    T t = a;
    a = b;
    b = t;
}

template <typename T>
bool next_permutation(T s, T e){

    static T p, q;
    for (p = e - 2; p >= s; --p)
    {
        if (*p < p[1])
            break;
    }
    if (p < s)
        return false;
    for (q = p + 1; q < e; ++q)
    {
        if (*q <= *p)
            break;
    }
    swap(*p++, *--q);
    for (q = e - 1; p < q;)
        swap(*p++, *q--);
    return true;
}

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

    int a[] = {2, 1, 3, 4}, n = sizeof(a) / sizeof(int);
    do {
        for (int i = 0; i < n - 1; ++i)
            printf("%d ", a[i]);
        printf("%d\n", a[n - 1]);
    } while(next_permutation(a, a + n));
    return 0;
}