龐果網排列搜索問題：C語言全排列實現與性能優化探討

問題背景

在龐果網（Pongo）的編程挑戰中，有一道關於排列搜索的題目：給定一個包含 n 個元素的數組 a，它恰好是 0..n-1 的一個排列。再給定四個索引 b[0]、b[1]、b[2]、b[3]，要求計算有多少個排列 a 滿足以下條件：

(a[a[b[0]]]*b[0] + a[a[b[1]]]*b[1] + a[a[b[2]]]*b[2] + a[a[b[3]]]*b[3]) % n == k

輸入參數為 N, K, B0, B1, B2, B3，其中 4 <= N < 12，0 <= K, B0, B1, B2, B3 < N。

初始解法：遞歸全排列

最直觀的方法是生成所有 N! 個排列並逐一檢查。以下是使用遞歸實現全排列的 C 代碼：

#include <stdio.h>
#define MAX_N 11

int a[MAX_N] = {0};
int g_count = 0;
int g_N, g_K, g_B0, g_B1, g_B2, g_B3;

void swap(int i, int offset) {
    int temp = a[i];
    a[i] = a[offset];
    a[offset] = temp;
}

void perm(int offset) {
    if (g_N - 1 == offset) {
        g_count += (a[a[g_B0]]*g_B0 + a[a[g_B1]]*g_B1 + a[a[g_B2]]*g_B2 + a[a[g_B3]]*g_B3) % g_N == g_K;
        return;
    }
    for (int i = offset; i < g_N; ++i) {
        swap(i, offset);
        perm(offset + 1);
        swap(i, offset);
    }
}

int howmany(int N, int K, int B0, int B1, int B2, int B3) {
    g_N = N; g_K = K; g_B0 = B0; g_B1 = B1; g_B2 = B2; g_B3 = B3;
    for (int i = 0; i < N; ++i) a[i] = i;
    perm(0);
    return g_count;
}

性能瓶頸分析

當 N=11 時，排列總數為 11! = 39,916,800。在 Linux Mint 16 (64-bit, Core 2 Duo) 上運行約需 2.3 秒，而在 Windows 上則需 7-8 秒，超過了典型的 3 秒時限。主要開銷在於：

• 遞歸函數調用開銷大
• 每次排列完成都要計算雙重索引 a[a[b[i]]] 並進行取模運算
• 缺乏剪枝策略，必須遍歷所有排列

優化方向探討

1. 迭代式排列生成

使用 next_permutation (C++) 或手寫迭代版全排列可消除遞歸開銷，通常能提升 2-3 倍速度。

2. 預計算與查表

由於 b[0..3] 固定，可預先計算所有可能的 a[a[x]] 組合，但在排列生成過程中 a 不斷變化，難以直接應用。

3. 狀態壓縮動態規劃 (DP with Bitmask)

考慮到 N < 12，可用 2^N 狀態表示已選數字集合。狀態 dp[mask][sum] 表示已選集合為 mask 時，部分和對 N 取模為 sum 的方案數。但條件涉及 a[a[b[i]]]，即雙重索引，使得狀態轉移非平凡，需進一步數學變換。

4. 剪枝優化

在遞歸過程中，若已確定的部分位置導致最終表達式無法滿足模條件，可提前回溯。但由於模運算的非單調性，剪枝條件較難構造。

結語

本題展示了全排列暴力解法在 N=11 邊界上的性能掙扎。對於競賽編程，掌握遞歸全排列是基礎，但面對嚴格時限時，需結合問題特性設計剪枝、DP 或數學優化。歡迎大神提供更優解法！