/*==========================================================
設有n個整數的集合{1,2,3，......,n}，從中任意選擇r個數進行排列。
其中r<n，請列出所有排列。
思路：遞歸r層，每層選擇一個數放到a[]。當遞歸到r層時得到一組排列。
在每一層中做選擇的時候，要把所有可能的選擇都進行嘗試。
具體看代碼。
============================================================*/ 1 #include <stdio.h>
2 #include <stdlib.h>
3 int num=0,a[10001]={0},n,r;
4 int b[10001]={0}; // a[]是選擇的r個數，b[i]是标志i是否已經被選中
5 //假如，待選擇的n個數并非1~n，而是c[]中的n元素。則a[]儲存被選中的數的下标即可。
6
7 void search(int k);//遞歸r層，每層選擇一個數放到a[]。當遞歸到r層時得到一組排列
8 void print(); //輸出一組排列的方案
9
10 int main()
11 {
12 scanf("%d%d",&n,&r);
13 search(1);
14 printf("總的方案數：%d\n",num);
15 return 0;
16 }
17 void search(int k)//遞歸r層，每層選擇一個數放到a[]。當遞歸到r層時得到一組排列
18 {
19 int i;
20 for(i=1;i<=n;i++)
21 {
22 if(b[i]==0)
23 {
24 a[k]=i; //選擇i作為第k個數字
25 b[i]=1; //辨別i已經被使用過
26 if(k==r) { num++; print(); }//得到一個方案，則方案數加1并輸出方案。
27 else search(k+1); //尚未找夠r個數字，繼續尋找第k+1個數字
28 b[i]=0; //還原現場：辨別i沒被使用過。
29 }
30 }
31 }
32 void print() //輸出一組排列的方案
33 {
34 int i;
35 for(i=1;i<=r;i++)
36 printf("%d ",a[i]);
37 printf("\n");
38 } 缺陷：
（1）這裡隻能是固定地選擇1~n中的r個數字，不是輸入的n個數字中選r個。
（2）n個數字不能有重複的元素存在
對缺陷（1），可以考慮把n個數字放在c[]，然後a[]存儲被選中的元素的下标。
例如a[i]=x表示c[x]被選中。b[i]=1表示c[i]被選中。
這樣一來，在選擇判斷的時候使用b[],在輸出的時候使用a[]。
對缺陷（2），可以看看“有重複元素的排列”. 上面的代碼是可以生成遵守字典序的全排列的。 下面的算法效率較高，但是不符合嚴格的字典序： 來源：https://subetter.com/ 1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 void FullPermutation(int array[], int left, int right)
5 {
6 if (left == right)
7 {
8 for (int i = 0; i < 4; i++)
9 cout << array[i] << " ";
10 cout << endl;
11 }
12 else
13 {
14 for (int i = left; i <= right; i++)
15 {
16 swap(array[i], array[left]);
17 FullPermutation(array, left + 1, right);
18 swap(array[i], array[left]);
19 }
20 }
21 }
22 int main()
23 {
24 int array[4] = { 1,2,3,4 };
25 FullPermutation(array, 0, 3);
26 return 0;
27 } 利用C++算法庫函數實作全排列
（下面的内容是原作者整理的。）
熟悉 C++ 的朋友肯定知道另一種更簡單，更完美的全排列方法。
定義于檔案 <algorithm> 内的兩個算法函數：
- next_permutation，對于目前的排列，如果在字典序中還存在下一個排列，傳回真，并且把目前排列調整為下一個排列；如果不存在，就把目前排列調整為字典序中的第一個排列（即遞增排列），傳回假。
- prev_permutation，對于目前的排列，如果在字典序中還存在上一個排列，傳回真，并且把目前排列調整為上一個排列；如果不存在，就把目前排列調整為字典序中的最後一個排列（即遞減排列），傳回假。
1 /**
2 *
3 * author : 劉毅（Limer）
4 * date : 2017-05-31
5 * mode : C++
6 */
7 #include <iostream>
8 #include <algorithm>
9 using namespace std;
10 void FullPermutation(int array[])
11 {
12 do
13 {
14 for (int i = 0; i < 4; i++)
15 cout << array[i] << " ";
16 cout << endl;
17 } while (next_permutation(array, array + 4));
18 }
19 int main()
20 {
21 int array[4] = { 1,2,3,4 };
22 FullPermutation(array);
23 return 0;
24 }