枚舉生成排列的方法總結

1.    利用遞歸的方法枚舉 1 ~ n 的所有不重數排列

思路大概就是對一個大小為n的容器，定義一個遞歸方法 。

每次通過 1 ~ 9 的順序不斷進行放置 ，放置條件為這個數字在容器裡面沒有出現過 。 （ 遞歸方法 ）

直到放滿容器為止列印出目前滿足的排列 。 （遞歸邊界條件）

實作代碼如下：

/*
    利用遞歸的方法，求 1 ~ n 的全排列
 */
#include <iostream>
#include <cstdlib>

using namespace std;

long long Count;                        // 定義一個計數器，計數排列種數；

void Printf_Permutation(int n, int cur, int *Num) {     // 遞歸函數；
	if (cur == n) {                     // 遞歸邊界；
		cout << "Num " << Count + 1 << " -> ";
		for ( int i = 1; i <= n; ++i ) {
			cout << Num[i];
			i == n ? cout << endl : cout << " ";

		}
		Count++;
	}
	else {
		for ( int i = 1; i <= n; ++i ) {     // 循環和遞歸調用嵌套的運用形式；
			int ok = 1;
			for ( int j = 1; j <= cur; ++j ) {   // 判斷要填進去的數字是不是已經填過；
				if (i == Num[j]) ok = 0;
			}
			if (ok) {
				Num[cur + 1] = i;       // 吧滿足條件的數字填進去，然後遞歸調用；
				Printf_Permutation(n, cur + 1, Num);
			}
		}
	}
}

int main( int argc, char const *argv[] ) {
	int n;
	cin >> n;
	int *Num = (int *)malloc(sizeof(int) * ( n + 1 ));  // 動态配置設定一個數組；

	Printf_Permutation(n, 0, Num);
	cout << "The All Of Permutation is " << Count << endl;
	return 0;
}
           

思考：部落客分析這道題目的時候突然腦洞打開，試想想：遞歸能不能看成是循環層數未知（自動擷取）的進階循環體結構。

2.    利用遞歸的方法枚舉 1 ~ n 的所有可重數排列

​如果把問題改成：輸入數組P，并按字典序輸出數組A各元素的所有全排列。

那麼問題也很簡單

隻需要把上面代碼的 i == Num[j] 改成 setN[i] == Num[j]  ,  Num[cur + 1] = i 改成 Num[cur + 1] = setN[i] 然後在 輸入待排列的數組setN的時候排好序 。

為了可以出現可重的排序，是以能夠遞歸的判斷條件也要改成  countN < CountNum[setN[i]  // 判斷已經填進容器得某個元素個數是否小于它原本有的元素個數。

為了避免出現 1 1 和 1 1 未兩種情況的現象發生，是以必須在循環下面加一條判斷條件  if ( i == 1 || setN[i] != setN[i - 1])  即隻有不同的數字才能作為不用的排列填充。

實作代碼如下：

/*
    利用遞歸的方法，求 1 ~ n 的全排列
 */
#include <iostream>
#include <cstdlib>

using namespace std;

long long Count;                        // 定義一個計數器，計數排列種數；

void Printf_Permutation(int n, int cur, int *Num) {     // 遞歸函數；
	if (cur == n) {                     // 遞歸邊界；
		cout << "Num " << Count + 1 << " -> ";
		for ( int i = 1; i <= n; ++i ) {
			cout << Num[i];
			i == n ? cout << endl : cout << " ";

		}
		Count++;
	}
	else {
		for ( int i = 1; i <= n; ++i ) {     // 循環和遞歸調用嵌套的運用形式；
			int ok = 1;
			for ( int j = 1; j <= cur; ++j ) {   // 判斷要填進去的數字是不是已經填過；
				if (i == Num[j]) ok = 0;
			}
			if (ok) {
				Num[cur + 1] = i;       // 吧滿足條件的數字填進去，然後遞歸調用；
				Printf_Permutation(n, cur + 1, Num);
			}
		}
	}
}

int main( int argc, char const *argv[] ) {
	int n;
	cin >> n;
	int *Num = (int *)malloc(sizeof(int) * ( n + 1 ));  // 動态配置設定一個數組；

	Printf_Permutation(n, 0, Num);
	cout << "The All Of Permutation is " << Count << endl;
	return 0;
}