全排列及相关扩展算法（七）——组合数的字典序（另含全章代码整理）

1.引入概念：要列出一个集合{1,2,3,4}的所有子集是很容易的，我们可以按照二进制数的顺序，0000，0001，0010，0011，0100，0101，0110，0111......来表示我们要取的元素，其中0表示不取，1表示取，这样就获得了一个顺序。而组合也包含在这个顺序当中。我们看从{1,2,3,4}中选取两个元素的所有组合：
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111.

蓝色标记的是我们所取的组合。对应的顺序便是｛3，4｝｛2，4｝｛2，3｝｛1，4｝｛1，3｝｛1，2｝我们可以用字典序对这些组合进行排序：{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}.共6种。按照我的习惯，我们先看看我们平常列举组合数所采取的策略。比如说1，2，3，4，5取3个元素的组合。我们先从小的取：1，2，3.再把最后一个数改变:1,2,4;1,2,5.当到达5之后，含有1，2的所有组合已经被罗列完了。改变2为3，1，3，4；1，3，5；此时我们不能再选择2进行罗列，否则会重复。改变3为4，此时2和3都不能放入，1，4，5.改变4为5时，2，3，4都不能放入，不存在组合了。这时改变1为2。之后不能再选择1罗列。所以:对于一个组合C1C2C3C4...Cr(每个代表一个数，一共r个数，代表一个组合，数从[1,n]中选)，由于一个组合自身是不讲顺序的，我们可以对组合进行升序排列，使得C1

2.性质：

C(r - m)到达n - m后就不能再递增上去。由k = r - (r - k)得到
C(k)到达n - (r - k) = n - r + k 后就不能再递增上去。
那么，对于C1C2C3C4...Cr，我们从Cr开始向前找，直到找到有Ci < n - r + i，并执行
Ci = Ci + 1。由于所有的组合都已经强制升序，所以Cj= Ci + (j-i),j = i+1,i+2,...r即它后面的每一项都比前一项大1。由于Ci< n -r + i，Cr = Ci + (r - i) <=n(因为Ci比原来大了1)，所以构造出来的新的C1C2C3C4...Cr仍是[1,n]中选r个元素的一个组合，而且显然它在原组合的字典序后。 由此，我们构造出了一个排在原组合的字典序后面的组合。接下来证明它是紧邻着原组合的。

3.证明：假设有一个组合B1B2B3B4...Br的前i-1个元素和C1C2C3C4...Cr一样，且在原组合字典序后，在我们构造的字典序前，那么必有新Ci > Bi > 原Ci，这是不可能的，因为新Ci= 原Ci + 1。同样不可能存在前i个元素一样但在新Ci字典序前的组合，因为强制排序后Cj 到Cr 的每个元素都是最小的。同样不可能存在前k个元素一样（k < i）但在新Ci字典序前的组合。

如果找不到有Ci < n - r + i，说明已经到达最后一个：n -r + 1,n - r + 2,...n.由此我们可以直接得到组合数的相对字典序。下一个组合算法代码：

bool Next_Combination(int A[], int n, int r)
{
int i;
sort(A, A + r);
for (i = r - 1; !(A[i]  0; i--);
if (i == 0)
return false;
A[i] = A[i] + 1;
for (int j = i + 1; j
4.参考文档
https://wenku.baidu.com/view/8c79a2facc17552706220880.html
PS：全章代码整理：
//https://wenku.baidu.com/view/8c79a2facc17552706220880.html
 
#include
#include
#include
#include
#include
#include
#include
#include   
#include 
using namespace std;
 
int Count = 0;
void Swap(int &a, int &b)
{
a == b ? 0 : a ^= b ^= a ^= b;
}
 
 
void Print(int A[],int n)
{
for (int i = 0; i < n; i++)
{
printf("%d%c", A[i], i == n - 1 ? 'n' : ' ');
}
}
void Permutation(int A[], int m, int n)
{
if (m == n)
{
//Print(A, n);
Count++;
}
else
{
for (int i = m; i < n; i++)
{
Swap(A[m],A[i]);
Permutation(A, m + 1, n);
    Swap(A[m],A[i]);
}
}
}
 
 
 
void Reverse(int A[],int a,int b)
{
while (a < b)
{
Swap(A[a], A[b]);
a++;
b--;
}
}
bool next_permutation(int A[], int n)
{
int i = n - 2;
while ((A[i + 1] <= A[i])&&i>=0)i--;
if (i<0)
{
Reverse(A,0,n-1);
return false;
}
else
{
int j = i+1;
while ((A[j] > A[i])&&j 1 ? x*factorial(x - 1) : 1; }
 
 
int* get_permutation_medium(int A[], int n)
{
int* temp = new int[n-1];
 
for (int i = 0; i < n-1; i++)
{
temp[i] = 0;
for (int j = i + 1; j <= n - 1; j++)
{
if (A[j] < A[i])
{
temp[i]++;
}
}
}
return temp;
}
 
int get_permutation_rank(int medium[],int n)
{
int rank = 0;
for (int i = 0; i < n - 1;i++)
{
rank += medium[i]* factorial(n - 1 - i);
}
return rank;
}
 
int* get_permutation(int medium[], int n)
{
int* temp = new int[n + 1];
int* permutation = new int[n + 1];
for (int i = 0; i <= n; i++)
{
permutation[i]=temp[i] = i == n ? 1 : medium[i] + 1;
}
 
for (int i = 0; i <= n ; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if (temp[j] <= temp[i])
{
temp[i]++;
permutation[i]++;
}
else
{
break;
}
}
sort(temp,temp + i+1, greater());
}
return permutation;
}
 
 
 
int* get_permutation_error(int medium[], int n)
{
int* temp = new int[n + 1];
for (int i = 0; i <= n; i++)
{
temp[i] = i == n ? 1 : medium[i] + 1;
}
 
for (int i = 0; i <= n; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if ((medium[j] <= (i == n ? 1 : medium[i])) || (temp[j] <= temp[i]))
{
temp[i]++;
}
}
}
return temp;
}
 
 
int* get_permutation_medium_plus(int A[], int n)
{
int* temp = new int[n];
 
for (int i = 0; i < n; i++)
{
temp[n-A[i]] = 0;
for (int j = i + 1; j <= n - 1; j++)
{
if (A[j] < A[i])
{
temp[n-A[i]]++;
}
}
}
 
return temp;
}
 
int get_permutation_rank_plus(int medium[], int n)
{
int rank = 0;
for (int i = 0; i < n-1; i++)
{
rank += medium[i];
rank *= n - i -1;
}
 
return rank;
}
 
int* get_permutation_plus(int medium[], int n)
{
int* temp = new int[n];
memset(temp, 0, n * sizeof(int));
for (int i = 0; i < n; i++)
{
int empty = -1,j=n;//防止末尾已经被占的情况故提前一位
while (empty < medium[i] && j >= 0)
{
j--;
if (temp[j] <= 0)
{
empty++;
}
}
temp[j] = n - i;
}
 
return temp;
}
 
 
 
bool Movable(int A[], bool direct[], int n) //direct参数用于接收每个元素移动方向的数组。
{
int max = 1;//初始化最大可移动数为1，因为规定1是最小的数，可以自己设定。
int pos = -1;//初始化最大可移动数的位置为-1.

for (int i = 0; i A[i + 1] && direct[i]) || (i> 0 && A[i] >A[i - 1] && !direct[i]))
{
max = A[i];
pos = i;
}
}

if (pos == -1)
return false;
if (direct[pos])
{
swap(A[pos], A[pos + 1]);
swap(direct[pos], direct[pos + 1]);
}
else
{
swap(A[pos], A[pos - 1]);
swap(direct[pos], direct[pos - 1]);
}
 

for (int i = 0; i max)
direct[i] = !direct[i];
}
return true;
}
void Full_Array(int A[], int n)
{
bool* direct = new bool[n]; //产生一个记录每个元素移动方向的数组
sort(A, A + n); //将原序列变成一个升序
for (int i = 0; i0; i--)
{
swap(A[i], A[i - 1]);
swap(direct[i], direct[i - 1]); 
//Print(A, n);
Count++;
}
else
for (int i = 0; i < n-1; i++)
{
swap(A[i], A[i + 1]);
swap(direct[i], direct[i + 1]);
//Print(A, n);
Count++;
}
} while (Movable(A, direct, n));
delete[]direct;
}
 
 
 
bool Next_Combination(int A[], int n, int r)
{
int i;
sort(A, A + r);
for (i = r - 1; !(A[i]  0; i--);
if (i == 0)
return false;
A[i] = A[i] + 1;
for (int j = i + 1; j