Permutation—全排列

l  簡介

一個全排列是從一個有限集中選取元素，組成一個有序的序列，并且所有的元素出現(xiàn)且僅出現(xiàn)一次。

l  全排列的計數(shù)

n  當集合中元素互異時，顯然全排列總共有n!個。

n  現(xiàn)在考慮集合中存在重復(fù)元素的情況：

1.     我們首先看一個簡單的例子。

2.        設(shè)例子中的全排列數(shù)為P，那么我們將這P個排列中重復(fù)的元素1看成互異的，假設(shè)標記為1和1’，那么對于每種排列都能生成P(2) = 2!個惟一的新排列，而這些新排列恰好構(gòu)成了3個互異元素的全排列，因此P = P(3) ÷P(2) = 3。

3.        假設(shè)n個元素的多重集合中有m個互異的元素，各元素出現(xiàn)的次數(shù)分別為a₁, a₂, … , a_m，且滿足(a₁ + a₂ + … + a_m) = n那么這個集合形成的全排列個數(shù)為

4.        當m = n時，上式的結(jié)果即為n!。

l  生成全排列

n  遞推生成：每次輸出當前序列的下個全排列，直到生成所有全排列。

1.     按字典序生成：生成輸入序列按字典序的下個全排列。

l  尋找從序列A末尾開始的最長非增連續(xù)子列S。保存子列S之前的一個元素為a，在上圖中，S = { 6, 5, 1 }，a = 4；

l  容易看出S是其元素的字典序最大全排列，如圖中的{ 6, 5, 1 }，因此無法通過在S內(nèi)部交換元素得到A的下個字典序全排列，因此只需找出a + S，即序列{ 4, 6, 5, 1 }中的下個全排列。從序列末尾開始，尋找第一個大于a的元素b，如圖中的5，交換a與b。這樣我們更新了S之前的一個元素，只要將S變?yōu)槠湓氐?span style="COLOR: #4f81bd; mso-themecolor: accent1">字典序最小全排列即可得到A的下個字典序全排列；

l  翻轉(zhuǎn)S，由于S為非增的（交換a與b后還是如此），那么翻轉(zhuǎn)后自然變成非減序列，即其元素的字典序最小全排列。

l  以上算法即C++中std::next_permutation函數(shù)的實現(xiàn)。

2.     無序生成：生成輸入序列的下個全排列，各全排列間并不遵循特定的順序。

未完，待續(xù)……