0. 前言

更新紀錄 :

• 2022 年 5 月 12 日進行第一次修正.

1. 全排列

設 \mathscr {E} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}, 記 \mathscr {E}_{i} 表示從 \mathscr {E} 中移除第 i 個元素以後的集合, 則 \mathscr {E}_{i} = \left \{ e_{1}, e_{2}, ..., e_{i - 1}, e_{i + 1}, ..., e_{n} \right \}. 設函數 P(\mathscr {E}) 表示集合 \mathscr {E} 的全排列, 那麼集合 \mathscr {E} 的全排列可以表示為 \displaystyle {e_{1}.P(\mathscr {E}_{1}), e_{2}.P(\mathscr {E}_{2}), ..., e_{n}.P(\mathscr {E}_{n})}. 其中, e_{i}.P(\mathscr {E}_{i}) (i = 1, 2, ..., n) 表示在集合 \mathscr {E}_{i} 的每一個全排列的第一個位置加上元素 e_{i}.

當 n = 1 的時候, 集合 \mathscr {E} 有且唯有一個元素 e, 即 \mathscr {E} = \left \{ e \right \}. 此時, 集合 \mathscr {E} 的全排列 P(\mathscr {E}) = \left \{ e \right \}; 當 n > 1 的時候, 集合 \mathscr {E} 的全排列 P(\mathscr {E}) = \left \{ e_{1}.P(\mathscr {E}_{1}), e_{2}.P(\mathscr {E}_{2}), ..., e_{n}.P(\mathscr {E}_{n}) \right \}.

接著, 我們需要想辦法得到幾個數字組合的全排列. 我們首先考慮, 當 n = 1 的時候, 可以直接輸出集合中的元素, 因為此時集合的全排列有且唯有一個. 當 n > 1 的時候, 我們每次從集合中去掉一個, 生成剩下元素的全排列. 這個思想比較難以理解, 我以演示的形式加上之前所說 n > 1 時全排列 P(\mathscr {E}) 的具體形式來講解.

不妨設 \mathscr {E} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}, 我們要對這個結合 \mathscr {E} 生成全排列 P(\mathscr {E}), 那麼 P(\mathscr {E}) 中的元素大致可以這樣去分類 : \displaystyle {e_{1}.P(\mathscr {E}_{1}), e_{2}.P(\mathscr {E}_{2}), ..., e_{n}.P(\mathscr {E}_{n})}. 也就是說, 第 1 類以 e_{1} 打頭, 第 2 類以 e_{2} 打頭, ..., 第 n 類以 e_{n} 打頭. 以第 1 類為例, 從 \mathscr {E} 中去掉 e_{1} 之後, 剩下的元素 e_{2}, e_{3}, ..., e_{n} 作全排列, 再將 e_{1} 加到每一個元素之前, 就形成了第 1 類, 也就是以 e_{1} 打頭的排列. 同理, 對 e_{2}, e_{3}, ..., e_{n} 使用同樣的操作, 就可以生成集合 \mathscr {E} 的全排列.

那麼從 \mathscr {E} 中去掉 e_{1}, 生成 \mathscr {E}_{1} 的全排列, 然後再在這些全排列之前加上 e_{1}, 就生成了以 e_{1} 打頭的排列, 說的那麼簡單, 但是去掉 e_{1} 之後的集合 \mathscr {E}_{1} 的全排列如何生成呢? 很簡單, 採用相同的方法, 從 \mathscr {E}_{1} 中移除一個元素 e_{i}, 生成 \mathscr {E}_{1i} 的全排列, 然後再在這些全排列之前加上 e_{i} 就可以了. 其中, i = 2, 3, ..., n. 這樣不斷操作, 直到集合 \mathscr {E} 被移除得只剩下一個元素, 這個時候直接就得到了這一個元素的排列, 然後分別在之前按順序地加上被移除的元素就可以了. 很容易地, 就得到了一個遞迴的解題方法.

當 n = 0 或著 n = 1 時, 集合 \mathscr {E} 中有且唯有一個元素, 其全排列的數量有且唯有一個, 即 \mathscr {E} 本身. 這是遞迴結束的標誌, 當然你會在後面看到 n = 0 這個條件並不成立

當 n > 1 時, 我們需要從集合中移除某一元素. 不妨按順序從左到右移除元素, 但是如果給定的是陣列, 那麼在 C++ 中, 我們沒有辦法直接讓陣列縮小, 因此我們選擇將要移除的元素交換到某一位置, 表示它已經被移除了. 按照從左至右的順序, 首先被移除的就是陣列中的第一個元素, 此時我們直接生成第二個元素開始到最後一個元素為止的全排列. 由於不能讓陣列縮小, 所以我們還需要另外一個變數 start 的幫助, 以標識出我們現在需要生成全排列的元素範圍 [start, N). 其中, start 是起始位置, N 表示陣列中元素的數量. 每次從範圍的最前面移除一個元素的時候, 就讓 start += 1. 如果移除某一元素之後, 剩餘元素的全排列生成完畢, 我們還需要將被移除的元素放回到原來的位置. 如果不換的話, 想像一下 : 如果要生成集合 {1, 2, 3} 的全排列, 若 start 位置表示的就是被移除的位置, 而 C++ 中又採用交換的方式進行移除 :

• 首先移除 1. 那麼也就是 1 和自己進行交換, 交換完畢之後的陣列仍然是 {1, 2, 3}, 並且生成集合 {2, 3} 的全排列
  • 同樣地, 移除第一個位置的 2, 也是和自己進行交換, 交換完畢之後得到 {2, 3}. 因為剩下的集合中只有 3 一個元素, 所以直接在得到的排列在前面加上 2, 得到排列 23
  • 然後移除第二個位置的 3, 和第一個位置的 2 作交換, 交換完畢之後得到 {3, 2}. 因為剩下的集合中只有 2 一個元素, 因此得到的排列再加上 3, 得到排列 32
  在排列 23 和 32 前面加上 1 可以得到排列 123, 132. 此時, 陣列中的元素順序是這樣的 : {1, 3, 2}
• 接著輪到第二個位置的 3 被移除了, 也就是把 3 和第一個位置中的 1 進行交換, 得到的陣列是 {3, 1, 2}. 接著生成 {1, 2} 的全排列
  • 移除第一個位置的 1, 也是和自己進行交換, 交換完畢之後得到 {1, 2}. 因為剩下的集合中只有 2 一個元素, 所以直接在得到的排列在前面加上 1, 得到排列 12
  • 然後移除第二個位置的 2, 和第一個位置的 1 作交換, 交換完畢之後得到 {2, 1}. 因為剩下的集合中只有 1 一個元素, 因此得到的排列再加上 2, 得到排列 21
  在排列 12 和 21 前面加上 3 可以得到排列 312, 321. 此時, 陣列中的元素順序是這樣的 : {3, 2, 1}, 到這裡為止都非常好
• 但是當要移除 3 的時候, 把 3 和目前第一個位置中的 1 作交換, 得到的陣列是 {1, 2, 3}, 接著又要生成 {2, 3} 的全排列, 再在前面加上 1, 這個我們第一步已經做過了

因為, 我們可以得到結論, 如果及時將元素放回原來的位置, 就會生成重複的排列. 最後, 我們來演示一下將元素交換回原來的位置之後, 正確的全排列如何生成. 如果要生成集合 {1, 2, 3} 的全排列 :

• 首先移除 1. 那麼也就是 1 和自己進行交換, 交換完畢之後的陣列仍然是 {1, 2, 3}, 並且生成集合 {2, 3} 的全排列
  • 同樣地, 移除第一個位置的 2, 也是和自己進行交換, 交換完畢之後得到 {2, 3}. 因為剩下的集合中只有 3 一個元素, 所以直接在得到的排列在前面加上 2, 得到排列 23. 之後再次作交換, 同樣也是第一個位置和 2 作交換, 陣列沒有變化, 還是 {2, 3}
  • 然後移除第二個位置的 3, 和第一個位置的 2 作交換, 交換完畢之後得到 {3, 2}. 因為剩下的集合中只有 2 一個元素, 因此得到的排列再加上 3, 得到排列 32. 之後再次作交換, 也就是 2 和第一個位置作交換, 陣列還原為 {2, 3}
  在排列 23 和 32 前面加上 1 可以得到排列 123, 132. 此時, 把 1 和第一個位置進行交換, 也就是自己和自己進行交換後, 陣列中的元素順序是這樣的 : {1, 2, 3}
• 接著輪到第二個位置的 2 被移除了, 也就是把 2 和第一個位置中的 1 進行交換, 得到的陣列是 {2, 1, 3}. 接著生成 {1, 3} 的全排列
  • 移除第一個位置的 1, 也是和自己進行交換, 交換完畢之後得到 {1, 3}. 因為剩下的集合中只有 3 一個元素, 所以直接在得到的排列在前面加上 1, 得到排列 13. 之後再次自己和自己作交換, 陣列沒有變化, 還是 {1, 3}
  • 然後移除第二個位置的 3, 和第一個位置的 1 作交換, 交換完畢之後得到 {3, 1}. 因為剩下的集合中只有 1 一個元素, 因此得到的排列再加上 3, 得到排列 31. 之後再次作交換, 也就是 1 和第一個位置進行交換, 陣列還原為 {1, 3}
  在排列 13 和 31 前面加上 2 可以得到排列 213, 231. 此時, 把 1 和第一個位置進行交換, 交換後陣列中的元素順序是這樣的 : {1, 2, 3}
• 最後輪到第三個位置的 3 被移除了, 也就是把 3 和第一個位置中的 1 進行交換, 得到的陣列是 {3, 1, 2}. 接著生成 {1, 2} 的全排列
  • 移除第一個位置的 1, 也是和自己進行交換, 交換完畢之後得到 {1, 2}. 因為剩下的集合中只有 3 一個元素, 所以直接在得到的排列在前面加上 1, 得到排列 12. 之後再次自己和自己作交換, 陣列沒有變化, 還是 {1, 2}
  • 然後移除第二個位置的 2, 和第一個位置的 1 作交換, 交換完畢之後得到 {2, 1}. 因為剩下的集合中只有 1 一個元素, 因此得到的排列再加上 2, 得到排列 21. 之後再次作交換, 也就是 1 和第一個位置進行交換, 陣列還原為 {1, 2}
  在排列 12 和 21 前面加上 3 可以得到排列 312, 321. 此時, 將 3 和第一個元素作交換後, 陣列還原為 {1, 2, 3}. 最終, 給我們的陣列是什麼樣, 我們歸還出去的陣列還是這個樣子

通過上面的遞迴思路, 我們已經大致解決了全排列的問題. 但是目前還有兩個問題, 首先是如果給定的陣列大小為 0 怎麼辦, 其次是怎麼實作 e_{i}.P(\mathscr {E}_{i}), 即在程式中實現在排列之前加上一個元素.

針對第一個問題, 我們可以採用陣列的參考. 某些編碼器為陣列進行了拓展, 支援了大小為 0 的陣列. 但是大小為 0 的陣列並不能在函式之間傳遞, 所以當我們使用陣列的參考的時候, 我們並不需要進行額外的條件判斷. 但是如果你不使用陣列, 而是使用類似於 C++ 標準樣板程式庫中的 std::vector 或著 std::array 這樣的物件, 這時候你就要進行大小的判斷. 不過針對 std::array 這樣, 陣列大小在編碼期就已經知道的物件, 我們可以使用 if constexpr避免運作期的效率降低. 針對第二個問題, 請你仔細分析我們之前對集合 {1, 2, 3} 進行全排列的全過程. 你會發現, 所以被移除的元素都在沒有被移除的元素的前面, 而且是每一個元素逐個被移除. 也就是說, 當移除某一個元素之後, 剩下的元素的全排列生成完畢, 只要加上移除的元素就可以了. 而這個移除的元素, 就位於剩下的元素的前面. 那麼, 如果我們要將全排列輸出到螢幕上, 很簡單, 直接輸出整個陣列即可.

#include <iostream>

using namespace std;
template <typename T, size_t N>
void permutation(T (&arr)[N], int start = 0) {
    if(start + 1 == N) {
        for(const auto &c : arr) {
            cout << c;
        }
        cout << endl;
        return;
    }
    for(auto i {start}; i < N; ++i) {
        swap(arr[i], arr[start]);
        permutation(arr, start + 1);
        swap(arr[i], arr[start]);
    }
}

全排列的時間複雜度其實是很顯然的, 因為全排列總共需要生成 n! 個結果, 因此其時間複雜度至少會有 \Omega(n!). 而通過上述程式碼, 我們發現剩下的操作的時間複雜度和元素數量其實沒有太大的關係, 因此上述程式碼產生全排列的時間複雜度上限為 O(n). 根據大 Θ 記法的定義, 上述程式碼的時間複雜度為 \Theta(n!).