Part 04 Algorithms About Counting 排列组合算法
covering 6.6 and more
Disclaim: the codes in this section are not tested, it just wants to show you the thoughts behind the algorithms
1. Generating Permutations 生成排列
给定某一个排列,生成按照字典序升序的下一个排列
先从后往前遍历,直到遇到不是降序的第一个数。然后用该数右边大于该数的数中最小的数替换该数,右边剩下的数(含刚刚换下来的数)升序重排即可。
代码:
void next_permutation(int* a, int n) // 上一个排列为a,a中有n个数,将a转化为下一个排列
{
// STEP 1 找到打破降序的第一个数
int i = n - 2;
for ( ; i >= 0; i--)
{
if (a[i] < a[i + 1])
break;
}
// STEP 2 找到该数右边最大的数
int k = n - 1;
for ( ; k > i; k--)
{
if (a[k] > a[i])
break;
}
// STEP 3 交换这两个数
int temp = a[i];
a[i] = a[k];
a[k] = temp;
// STEP 4 右边余下的数升序重排
sort(a + i, a + n);
}
2. Find the ordinal number for the given permutation 给定排列求序号
基本思想:算出有多少个排列比给定排列小
例如:整数1~k的一个排列,求其序号
首先,1到放在第一位,会有个排列
其次,1到放在第二位,会有个排列
之后,1到放在第三位,会有个排列
……
全部加起来,即得到序号
代码:
int index_of_permutation(int* a, int n)
{
// 递推算好1~(n-1)的阶乘,做好准备
int factorial[n];
factorial[0] = 1;
for (int i = 1; i < n; i++)
factorial[i] = factorial[i - 1] * i;
// 计算答案
int res = 0;
for (int i = 0; i < n; i++)
res += (a[i] - 1) * factorial[n - i - 1];
return res;
}
3. Find the permutation given the ordinal number 给定序号求排列
基本思想:逐位确定
例如:1234排列的第9号
假设第一位是1,1___
,能数到个,没有达到9,故第一位至少为2
假设第一位是2,2___
,能数到个,到达了9,故第二位为2
假设第二位是1,21__
,能数到个,没达到9,故第二位至少为3
假设第二位为3,23__
,能数到个,达到了9,故第二位为3
假设第三位为1,2314
,能数到个,因此找到所需数为2314
代码:
int* permutation_from_index(int index, int n)
{
// 递推算好1~n的阶乘,做好准备
int factorial[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++)
factorial[i] = factorial[i - 1] * i;
// 构建答案
int *res = new int[n];
bool used[n + 1];
memset(used, 0, sizeof(used));
for (int i = 0; i < n; i++) // 尝试第i位
{
for (int j = 1; j <= n; j++) // 尝试1~n
{
if (!used[j])
if (factorial[n - i - 1] >= index + 1)
break;
else
index -= factorial[n - i - 1];
}
res[i] = j;
used[j] = true;
}
return res;
}
4. Generating Combinations 生成组合
4.1. 位串表示下的生成组合
计算机中可以使用位串来表示组合,因此我们只需生成下一个位串即可
这就等价于二进制下加1
当然int
范围内的我们可以直接加1,但是考虑更加一般化的情景,比如储存在数组或者链表中的位串
代码如下:
void next_bit_string(int* b, int n)
{
for (int i = n - 1; i >= 0; i--)
{
if (b[i] == 1)
b[i] = 0;
else
{
b[i] = 1;
break;
}
}
}
4.2. 常规数字数组下的生成组合
如果单纯是用数组存放的组合,也是可以生成排列的,算法如下(规定每个有效的数组中元素都是升序排列的):
void next_r_combination(int* a, int n, int r)
{
for (int i = r - 1; i > 0; i--)
{
if (a[i] != n - r + 1 + i)
{
a[i]++;
for (int j = i + 1; i < r; i++)
a[j] = a[i] + j - i;
break;
}
}
}