1. 前言

本文介紹了常用的排列組合算法，包括全排列算法，全組合算法，m個數選n個組合算法等。

2. 排列算法

常見的排列算法有：
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法
(E)遞歸法

介紹常用的兩種：

(1) 字典序法

對給定的字符集中的字符規定了一個先后關系，在此基礎上按照順序依次產生每個排列。

[例]字符集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。

生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有字典順序中相鄰的字符串。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。

算法思想：

設P是[1,n]的一個全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|Pi<Pi+1}, k=max{i|Pi>Pj} ,對換Pj，Pk，將Pj+1…Pk-1PjPk+1…Pn翻轉， P'= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一個

例子:839647521的下一個排列.

從最右開始,找到第一個比右邊小的數字4(因為4<7，而7>5>2>1),再從最右開始,找到4右邊比4大的數字5(因為4>2>1而4<5),交換4、5,此時5右邊為7421,倒置為1247,即得下一個排列:839651247.用此方法寫出全排列的非遞歸算法如下

該方法支持數據重復，且在C++ STL中被采用。

(2) 遞歸法

設一組數p = {r1, r2, r3, … ,rn}, 全排列為perm(p)，pn = p