忽若流星

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ù)分別為a₁, a₂, … , a_m，且滿足(a₁ + a₂ + … + a_m) = 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ù)……