递归实现排列型枚举(全排列问题) - 详解

原题链接

点我跳转

题解

本题最容易想到的两种解法是 DFS 与 STL 这两种解法。我对前两种解法不作解释。

普通解法(dfs):

#include 
int n, a[19];
bool st[19];
void dfs(int k) {
    if (k > n) {
        for (int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        puts("");
        return ;
    }
    for (int i = 1; i <= n; i++) {
        if (st[i]) continue;
        st[i] = true, a[k] = i;
        dfs(k+1);
        st[i] = false;
    }
}
int main() {
    scanf("%d", &n);
    dfs(1);
    return 0;
}

STL 解法:

#include 
#include 
int n, a[10];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        a[i] = i;
    do {
        for (int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        puts("");
    } while (std::next_permutation(a+1, a+n+1));
    return 0;
}

下面介绍两种比较烧脑的方法:

烧脑: 纯位运算解法

其实这种方法也并不是很难理解, 只是把 OIer 通常写的 a[] 换成了 (long long)a, 实现了空间上的大幅优化. 读者可以将这个代码与上面第一个代码比对, 以更好地理解这个代码.

#include 
long long a;
int n, st;
void dfs(int k) {
    if (k > n) {
        for (int i = 1; i <= n; i++)
            printf("%lld ", (a>>4*i) & 0xF);
        puts("");
        return ;
    }
    for (long long i = 1; i <= n; i++) {
        int x = 1 << i;
        if (st & x) continue;
        st |= x, a |= i << (4*k);
        dfs(k+1);
        st ^= x, a ^= i << (4*k);
    }
}
int main() {
    scanf("%d", &n);
    dfs(1);
    return 0;
}

烧脑: for 循环解法:

这种解法比较生僻, 值得仔细介绍. 虽然这种方法的代码量要比前三种都大, 但是它有几点好处:

• 优化了时间复杂度(但幅度不大)
• 锻炼思维
• 装逼

上面的是 for, 下面的是 dfs

下面正式开始分析这个算法.

我们可以通过列表的方式找出规律. 不妨设 n=6, 那么全排列的前 5 5 5 项就是:

然后我们标出每次交换的两个数标记出来:

观察这几对数, 可以得出这样的算法: 从右往左看, 找出第一个降序的较小的数字 a, 拿最右边大于 a 的数字和它交换一下, 剩余的右边反转.

例如, 若要求解全排列中第六组与第七组数, 那么应该这样求:

图例: 蓝色与绿色部分为待交换的两个数, 标为黄色的数为待反转的数.

第六组变化过程

第七组变化过程

至此, 算法分析完毕.

#include 
const int N = 10;
int n, cnt = 1, a[N], b[N];
void swap(int &a, int &b) { a ^= b ^= a ^= b; }
void reverse(int st, int ed) {
    for (int i = st, j = ed; i < j; i++, j--) 
        swap(a[i], a[j]);
}
bool check() {
    for (int i = cnt+1; i <= n; i++)
        if (a[i] > a[i-1]) 
            return true;
    cnt++;
    return false;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        a[i] = i, printf("%d ", a[i]);
    puts("");
    for (int i = 1, x, y; i <= n; i++) { // 后 i 个
        while (check()) {
            bool flag = false;
            for (int j = n-1; j >= 1; j--) {
                for (int k = n; k > j; k--) {
                    if (a[k] > a[j]) {
                        x = j, y = k;
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            } // 找出第一个降序
            swap(a[x], a[y]);
            reverse(x+1, n);
            for (int j = 1; j <= n; j++)
                printf("%d ", a[j]);
            puts("");
        }
    }
    return 0;
}