转自台湾师范大学acm课程
Enumerate all n-tuples
列舉重複排列。這裡示範：列舉出「數字 1 到 10 選擇五次」全部可能的情形。
製作一個陣列，用來存放一組可能的排列（數據）。
int solution[5];
例如 solution[0] = 4 表示第一個抓到的數字是 4 ， solution[4] = 9 表示第五個抓到的數字是 9 。陣列中不同的格子，就是 solution vector 當中不同的維度。
遞迴程式碼設計成這樣：
int solution[5]; // 用來存放一組可能的數據
void print_solution() // 印出一組可能的數據
{
for (int i=0; i<5; i++)
cout << i << ' ';
cout << endl;
}
void backtrack(int n) // n 為現在正在列舉的維度
{
// it's a solution
if (n == 5)
{
print_solution();
return;
}
// 逐步列舉數字1到10，並且各自遞迴下去，列舉之後的維度
solution[n] = 1;
backtrack(n+1);
solution[n] = 2;
backtrack(n+1);
......
solution[n] = 10;
backtrack(n+1);
}
int main()
{
backtrack(0);
}
輸出結果會照字典順序排列。附送一張簡圖：
注解： 其实就是利用递归来打印出整个字典顺序。注意递归函数中的顺序和递归停止条件。
Permutation
permutation 是「排列」的意思，便是數學課本中「排列組合」的排列。但是這裡並不是要計算排列有多少種，而是實際列舉出所有的排列：
現在有一個集合，裡面有 1 到 n 的數字，列出所有數字的排列，同樣的排列不能重複列出來。例如 {1,2,3} 所有的排列就是 {1,2,3} 、 {1,3,2} 、 {2,1,3} 、 {2,3,1} 、 {3,1,2} 、 {3,2,1} 。
permutation 的問題可以使用 backtracking 的技術來解決！
依序窮舉每個位置，針對每個位置，試著填入各種數字
一般來說， permutation 的程式碼都會長成這樣的格式：
int solution[MAX]; // 用來存放一組可能的答案
bool used[MAX]; // 紀錄數字是否使用過，用過為 true
void permutation(int k, int n)
{
if (k == n) // it's a solution
{
for (int i=0; i<n; i++)
cout << solution[i] << " ";
cout << endl;
}
else
{
for (int i=0; i<n; i++) // 試著將第 k 格填入各種數字
if (!used[i])
{
used[i] = true; // 紀錄用過的數字
solution[k] = i; // 將第 k 格填入數字 k
permutation(k+1, n); // iterate next position
used[i] = false; // 回收用完的數字
}
}
}
int main()
{
for (int i=0; i < MAX; i++) // initialization
used[i] = false;
permutation(0, 10); // 印出0~9，一共10個數字的所有排列
}
permutation 的問題都可以使用這段程式碼來解決。而且這支程式，是以字典順序來列舉出所有排列。所以它真的很有用，不妨參考看看。
依序窮舉每個數字，針對每個數字，試著填入各個位置
另外還有一種作法是生做這個樣子的：
int solution[MAX]; // 用來存放一組可能的答案
bool filled[MAX]; // 紀錄各個位置是否填過數字，填過為 true
void permutation(int v, int n)
{
if (v == n) // it's a solution
{
for (int i=0; i<n; i++)
cout << solution[i] << " ";
cout << endl;
}
else
{
for (int i=0; i<n; i++) // 試著將數字 v 填入各個位置
if (!filled[i])
{
filled[i] = true; // 紀錄填過的位置
solution[i] = v; // 將數字 v 填入第 i 格
permutation(v+1, n); // iterate next position
filled[i] = false; // 回收位置
}
}
}
int main()
{
for (int i=0; i<MAX; i++) // initialization
filled[i] = false;
permutation(0, 10); // 印出0~9，一共10個數字的所有排列
}
這也是一個不錯的方法，列出來提供大家參考。多接觸各式各樣的方法，能激發一些創意呢！
為了講解方便，以下的文章以一開始提到的方法當作基準。
字串排列
有個常見的問題是：列出字串 abc 的所有排列，要依照字典順序列出。其實這就跟剛才介紹的東西大同小異，只要稍加修改程式碼即可。
char s[3] = {'a', 'b', 'c'}; // 字串，需要先由小到大排序過
char solution[3]; // 用來存放一組可能的答案
bool used[3]; // 紀錄該字母是否使用過，用過為 true
void permutation(int k, int n)
{
if (k == n) // it's a solution
{
for (int i=0; i<n; i++)
cout << solution[i];
cout << endl;
}
else
{
// 針對solution[i]這個位置，列舉所有字母，並各自遞迴
for (int i=0; i<n; i++)
if (!used[i])
{
used[i] = true;
solution[k] = s[i]; // 填入字母
permutation(k+1, n);
used[i] = false;
}
}
}
