Permutation—全排列
l 簡(jiǎn)介
一個(gè)全排列是從一個(gè)有限集中選取元素，組成一個(gè)有序的序列，并且所有的元素出現(xiàn)且僅出現(xiàn)一次。
l 全排列的計(jì)數(shù)
n 當(dāng)集合中元素互異時(shí)，顯然全排列總共有n!個(gè)。
n 現(xiàn)在考慮集合中存在重復(fù)元素的情況：
1. 我們首先看一個(gè)簡(jiǎn)單的例子。
2. 設(shè)例子中的全排列數(shù)為P，那么我們將這P個(gè)排列中重復(fù)的元素1看成互異的，假設(shè)標(biāo)記為1和1’，那么對(duì)于每種排列都能生成P(2) = 2!個(gè)惟一的新排列，而這些新排列恰好構(gòu)成了3個(gè)互異元素的全排列，因此P = P(3) ÷P(2) = 3。
3. 假設(shè)n個(gè)元素的多重集合中有m個(gè)互異的元素，各元素出現(xiàn)的次數(shù)分別為a1, a2, … , am，且滿足(a1 + a2 + … + am) = n那么這個(gè)集合形成的全排列個(gè)數(shù)為
4. 當(dāng)m = n時(shí)，上式的結(jié)果即為n!。
l 生成全排列
n 遞推生成：每次輸出當(dāng)前序列的下個(gè)全排列，直到生成所有全排列。
1. 按字典序生成：生成輸入序列按字典序的下個(gè)全排列。
l 尋找從序列A末尾開始的最長(zhǎng)非增連續(xù)子列S。保存子列S之前的一個(gè)元素為a，在上圖中，S = { 6, 5, 1 }，a = 4；
l 容易看出S是其元素的字典序最大全排列，如圖中的{ 6, 5, 1 }，因此無法通過在S內(nèi)部交換元素得到A的下個(gè)字典序全排列，因此只需找出a + S，即序列{ 4, 6, 5, 1 }中的下個(gè)全排列。從序列末尾開始，尋找第一個(gè)大于a的元素b，如圖中的5，交換a與b。這樣我們更新了S之前的一個(gè)元素，只要將S變?yōu)槠湓氐?span style="COLOR: #4f81bd; mso-themecolor: accent1">字典序最小全排列即可得到A的下個(gè)字典序全排列；
l 翻轉(zhuǎn)S，由于S為非增的（交換a與b后還是如此），那么翻轉(zhuǎn)后自然變成非減序列，即其元素的字典序最小全排列。
l 以上算法即C++中std::next_permutation函數(shù)的實(shí)現(xiàn)。
2. 無序生成：生成輸入序列的下個(gè)全排列，各全排列間并不遵循特定的順序。
未完，待續(xù)……