組合算法
非遞歸算法
組合算法的思路是開一個數(shù)組疏尿，其下標表示1到m個數(shù)榆鼠，數(shù)組元素的值為1表示其下標代表的數(shù)被選中，為0則沒選中俱笛。
初始化捆姜，將數(shù)組前n個元素置1，表示第一個組合為前n個數(shù)迎膜。
從左到右掃描數(shù)組元素值的“10”組合泥技，找到第一個“10”組合后將其變?yōu)椤?1”組合，同時將其左邊的所有“1”全部移動到數(shù)組的最左端磕仅。
當?shù)谝粋€“1”移動到數(shù)組的m-n的位置珊豹，即n個“1”全部移動到最右端時，就得到了最后一個組合榕订。
例如求5中選3的組合：
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
c++代碼如下：
class Combination {
public:
void combination(int n, int m) {
int *a = new int[n];
for (int i = 0; i < m; i++)
a[i] = 1;
for (int i = m; i < n; i++)
a[i] = 0;
bool tag = true;
while (tag) {
displayArray(a, n);
for (int i = 0; i < n - 1; i++)
if (a[i] == 1 && a[i + 1] == 0) {
tag = true;
a[i] = 0;
a[i + 1] = 1;
moveZeros(a, i);
break;
}
else
tag = false;
}
}
private:
void displayArray(int *a, int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
// 0到n-1店茶，把1移到最左邊
void moveZeros(int *a, int n) {
int left = 0, right = 0;
while (right < n) {
if (a[left] == 1)
left++;
else if (a[left] == 0 && a[right] == 1) {
int t = a[left];
a[left] = a[right];
a[right] = t;
left++;
}
right++;
}
}
};
遞歸算法
從n個數(shù)中選取編號最大的數(shù)，然后在剩下的n-1個數(shù)里面選取m-1個數(shù)劫恒，直到從n-(m-1)個數(shù)中選取1個數(shù)為止。
從n個數(shù)中選取編號次小的一個數(shù)仓手，繼續(xù)執(zhí)行1步梗劫，直到當前可選編號最大的數(shù)為m。
c++代碼如下:
class Combination {
public:
void combination(int n, int m) {
int *a = new int[n];
for (int i = 0; i < n; i++)
a[i] = 0;
func(a, n, m, n);
}
private:
void displayArray(int *a, int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
void func(int *a, int n, int m, const int N) {
if (m == 0) {
displayArray(a, N);
return;
}
for (int i = n - 1; i >= m - 1; i--) {
a[i] = 1;
func(a, i, m - 1, N);
a[i] = 0;
}
}
};
排列算法
遞歸算法
如果集合是{a,b,c},那么這個集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}族壳，顯然，給定n個元素共有n!種不同的排列.
如果給定集合是{a,b,c,d}趣些，可以用下面給出的簡單算法產生其所有排列仿荆，即集合(a,b,c,d)的所有排列有下面的排列組成：
（1）以a開頭后面跟著(b,c,d)的排列
（2）以b開頭后面跟著(a,c,d)的排列
（3）以c開頭后面跟著(a,b,d)的排列
（4）以d開頭后面跟著(a,b,c)的排列
這顯然是一種遞歸的思路，于是我們得到了以下的c++代碼實現(xiàn)：
class Permutation {
public:
void permutation(int n) {
int *a = new int[n];
for (int i = 0; i < n; i++)
a[i] = 0;
func(a, 1, n);
}
private:
void displayArray(int *a, int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
void func(int *a, int m, const int n) {
if (m == n + 1) {
displayArray(a, n);
return;
}
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
a[i] = m;
func(a, m + 1, n);
a[i] = 0;
}
}
}
};
非遞歸算法
<div class="div-border left-purple"> 全排列生成算法的一個重要思路喧务，就是將集合A中的元素的排列赖歌，與某種順序建立一一映射的關系，按照這種順序功茴，將集合的所有排列全部輸出庐冯。這種順序需要保證，既可以輸出全部的排列坎穿，又不能重復輸出某種排列展父，或者循環(huán)輸出一部分排列。
字典序就是用此種思想輸出全排列的一種方式玲昧。這里以A{1,2,3,4}來說明用字典序輸出全排列的方法栖茉。
首先，對于集合A的某種排列所形成的序列孵延，字典序是比較序列大小的一種方式吕漂。
以A{1,2,3,4}為例，其所形成的排列1234 < 1243尘应，比較的方法是從前到后依次比較兩個序列的對應元素惶凝，如果當前位置對應元素相同，則繼續(xù)比較下一個位置犬钢，直到第一個元素不同的位置為止苍鲜，元素值大的元素在字典序中就大于元素值小的元素。
上面的a1[1…4]=1234和a2[1…4]=1243玷犹，對于i=1,i=2混滔，兩序列的對應元素相等，但是當i=2時歹颓，有a1[2]=3 < a2[2]=4坯屿，所以1234 < 1243。
使用字典序輸出全排列的思路是巍扛，首先輸出字典序最小的排列愿伴，然后輸出字典序次小的排列，……电湘，最后輸出字典序最大的排列隔节。
這里就涉及到一個問題鹅经，對于一個已知排列，如何求出其字典序中的下一個排列怎诫。這里給出算法瘾晃。
對于排列a[1…n]，找到所有滿足a[k] < a[k+1] (0 < k < n-1)的k的最大值幻妓，如果這樣的k不存在蹦误，則說明當前排列已經是a的所有排列中字典序最大者，所有排列輸出完畢肉津。
在a[k+1…n]中强胰，尋找滿足這樣條件的元素l，使得在所有a[l]>a[k]的元素中妹沙，a[l]取得最小值偶洋。也就是說a[l]>a[k]，但是小于所有其他大于a[k]的元素距糖。
交換a[l]與a[k].
對于a[k+1…n]玄窝，反轉該區(qū)間內元素的順序。也就是說a[k+1]與a[n]交換悍引，a[k+2]與a[n-1]交換恩脂，……，這樣就得到了a[1…n]在字典序中的下一個排列趣斤。
這里我們以排列a[1…8]=13876542為例俩块，來解釋一下上述算法。首先我們發(fā)現(xiàn)浓领，1(38)76542典阵，括號位置是第一處滿足a[k] < a[k+1]的位置，此時k=2镊逝。
所以我們在a[3…8]的區(qū)間內尋找比a[2]=3大的最小元素，找到a[7]=4滿足條件嫉鲸，交換a[2]和a[7]得到新排列14876532撑蒜，對于此排列的3～8區(qū)間，反轉該區(qū)間的元素玄渗，將a[3]-a[8]座菠，a[4]-a[7]，a[5]-a[6]分別交換藤树，就得到了13876542字典序的下一個元素14235678浴滴。</div>
下面是該算法的實現(xiàn)代碼：
class Permutation {
public:
void permutation(int n) {
int *a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
while (true) {
displayArray(a, n);
//找到k
int k = n - 2;
while (k != -1 && a[k] > a[k + 1])
k--;
if (k == -1)
return;
// 交換比k稍大的數(shù)
int l = k + 1;
for (int i = k + 1; i < n; i++)
if (a[i] > a[k] && a[i] < a[l])
l = i;
int t = a[k];
a[k] = a[l];
a[l] = t;
//反轉
for (int i = 1; 2 * i < n - k; i++) {
int t = a[k + i];
a[k + i] = a[n - i];
a[n - i] = t;
}
}
}
private:
void displayArray(int *a, int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
};
