如何計算排列方法數，其中相同元素不能相鄰？

01-05

首先聲明:編程之美比賽已經結束了，這個問題不違反比賽規則。
問題:把a1個1、a2個2、……、an個n排成一排，其中相同的數字不能相鄰，求方法數。

匿名用戶的動態規劃解法是正解，不過直接看程序不容易看懂，我來用人話解釋一遍。

首先澄清一點題意：從題主的描述來看，相同的數交換位置算同一種擺法。不過從匿名用戶的程序來看，題目是以撲克牌為背景的，點數相同的牌還有花色的區別。我就按後一種題意來講了。

先來設計一種樸素的狀態：用 $(a_1, a_2, ..., a_n)$ 表示還剩下 $a_1$ 張1、 $a_2$ 張2、……、 $a_n$ 張n需要擺放。

考慮到不允許相同的數字相鄰，還需要在狀態中補充一個數k，表示第一張牌不能是k點（以下稱k為「禁手」）。

這樣，一個狀態對應的擺法數就是：

$C(a_1,a_2,cdots,a_n,k) = sum_{substack{1 le i le n \ i e k, a_i > 0}} a_i cdot C(a_1, a_2, cdots, a_i - 1, cdots, a_n, i)$

這裡的下標i就枚舉了第一張牌是幾點，它不能取k，也不能取已經一張不剩的牌。第一張牌選了i點後，下一張牌的「禁手」就變成i了。

動態規劃的初始條件是 $C(0, cdots, 0, *) = 1$ （禁手是幾都無所謂），

而待求的擺法數是 $C(a_1, a_2, cdots, a_n, 0)$ （0表示無禁手）。

這種狀態設計方法能夠解決問題，但明顯有大量的冗餘狀態：

把狀態中的各個 $a_i$ 交換（若涉及禁手，則也要做相應調整），擺法數是一樣的。

其實，狀態中每種牌還剩幾張並不重要，重要的是有幾種牌還剩1張、有幾種牌還剩2張……等等。

所以我們把狀態修改成這樣：用 $(b_1, b_2, ..., b_m, k)$ 表示還有 $b_1$ 種牌剩餘1張， $b_2$ 種牌剩餘2張，……， $b_m$ 種牌剩餘m張，禁手牌剩餘k張。m取各 $a_i$ 的最大值就夠了。

這樣，狀態轉移方程就變成了：

$C(b_1, b_2, cdots, b_m, k) = sum_{substack{1 le i le m, \ b_i > delta_{i,k}}} (b_i - delta_{i,k}) cdot i cdot C(b_1, b_2, cdots, b_{i-1} + 1, b_i - 1, cdots, b_m, i-1)$

這裡下標i表示選擇一種還剩i張的牌。定義 $delta_{i,k}$ 在i=k時取1，否則取0。求和式中的第一項表示有 $b_i$ 種牌可選（若禁手牌恰也剩餘i張，則少一種）；第二項i表示每種牌有i張不同花色可選；第三項是轉移後的狀態——剩餘i張的牌少了一種，而剩餘i-1張的牌多了一種，同時禁手牌（即剛剛選的牌）剩餘i-1張。

初始條件是仍是 $C(0,cdots,0,*) = 1$ ，待求狀態無禁手。

在實際編程的時候，為了保證僅計算有用的狀態，可以用記憶化搜索實現。

若不計不同花色的區別，只需去掉第一個狀態轉移方程右邊的 $a_i$ ，或第二個狀態轉移方程右邊的i。

編程之美那個題可以用dp來做。

#include & #include & using namespace std;


unsigned long long dp[14][14][14][14][5];

bool cal[14][14][14][14][5];

// b[x] 表示的是還有b[x]種牌還剩x張, forbid表示的禁手牌還剩下的數量 unsigned long long get_dp(int (b)[5], int forbid) { // cal 表示是否計算過 bool Cal = cal[b[1]][b[2]][b[3]][b[4]][forbid]; // 獲取Dp unsigned long long Dp = dp[b[1]][b[2]][b[3]][b[4]][forbid]; // 如果計算過，就返回記憶化Dp if (Cal) { return Dp; } // 標記為計算過 Cal = true; // Dp初始為0 Dp = 0; // 記錄是否還有牌 bool hascard = false; // 新的計數 int newb[5]; // 枚舉相同面值剩餘數目是 i for (int i = 1; i &<= 4; i++) { // 假如不存在任何面值剩餘 i 張，跳過 if (b[i] == 0) continue; // 有卡 hascard = true; // 複製計數 memcpy(newb, b, sizeof(newb)); // 剩餘數目是 i 的面值數減1 newb[i]--; // 剩餘數目是 i - 1 的面值數加1 newb[i - 1]++; // 遞歸，使用新的計數，下一張不能取的面值還有 i - 1 張 Dp += (b[i] - (i == forbid)) * i * get_dp(newb, i - 1); } // 如果沒卡，應該特殊處理為1，初始狀態 if (!hascard) { Dp = 1; } return Dp; } int main() { memset(cal, 0, sizeof(cal)); int T; cin &>&> T; for (int cas = 1; cas &<= T; cas++) { int N; int b[13]; memset(b, 0, sizeof(b)); cin &>&> N; while (N--) { char p; cin &>&> p; if (p == "A") { b[0]++; } else if (p == "T") { b[9]++; } else if (p == "J") { b[10]++; } else if (p == "Q") { b[11]++; } else if (p == "K") { b[12]++; } else { b[p - "1"]++; } cin &>&> p; } int newb[5]; memset(newb, 0, sizeof(newb)); for (int i = 0; i &< 13; i++) { newb[b[i]]++; } cout &<&< "Case #" &<&< cas &<&< ": " &<&< get_dp(newb, 0) &<&< endl; } }

我來簡單地描述一個時間/空間複雜度更低的做法，細節留給題主自己去推敲。

首先我把題目改成一個便於敘述的方式。

有 $N$ 種顏色的球，第 $i$ 個顏色的球有 $a_i$ 個，共 $M$ 個球（ $M = sum_{n=1}^{N}a_i$ ），求 $M$ 個球的排列方式使得不存在兩個相鄰的球同顏色。

做法也是動態規劃，思路是枚舉顏色，每次將相同顏色的球全部插入序列。

$F_{i, j}$ 表示插入到第 $i$ 個顏色，存在 $j$ 個 "相鄰相同的顏色的球"（也就是有 $j$ 個 "不合法空隙"）。那麼我們 DP 的到第 $i$ 個顏色時，枚舉將 $a_i$ 個球分到 $p$ 個非空組裡（插板法算方案數），然後枚舉這 $p$ 個組中有 $k$ 個組進入 "不合法空隙" 里。

最後答案是 $F_{N,0}$ 。

順便附一個可以提交本題的網址（鏈接中的題目每個球是不同的，所以最終答案還得乘一下排列數）：Problem - 4532