排列

求 n 个元素的全排列

使用 STL

这东西最先想到的必然是直接使用 STL 中的 next_permutation() 了，每执行一次都会把数组内的序列改为下一个排列，最后会输出 -1

1
2
3
4
5
6
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int sum = 0;
do{
    sum++;
    // 得到一个结果
}while(next_permutation(data,data+12));

使用递归（法一，不推荐）

这个方法应该是我高中的时候自己手搓出来的，性能很差劲，放在这里只是为了凑个数（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
int a[1000], v[1000], n, k; //A (n,k)
void dfs(int cnt, int num)
{
    for (int i = 1; i <= n; i++) //组合 for(int i = num+1; i <= n ;i++)
        if (!v[i])
        {
            a[cnt] = i;
            v[i] = 1;
            if (cnt == k) // 边界条件
            {
//                得到一个结果
//                for (int i = 1; i <= k; i++)
//                    cout << a[i];
//                cout << endl;
            }
            else
                dfs(cnt + 1, i);
            v[i] = 0;
        }
}
int main()
{
    cin >> n >> k;
    dfs(1, 0);
    return 0;
}

这个方法只能生成数据为 1~n 的结果，而如果原始数据不是前 n 个数字的话，可以使用索引的方法，即 cout << data[a[i]];

使用递归（法二，推荐）

这个方法就是书上的了，我测下来效果是最好的，基本思想就是拿每一层的第一个数跟后面的数依次交换

1
2
3
4
5
6
7
8
9
10
11
12
13
int Perm(int begin, int end)
{
    if (begin == end) // 得到一个结果
        return 1;
    int sum = 0;
    for (int i = begin; i <= end; i++)
    {
        swap(data[begin], data[i]);
        sum += Perm(begin + 1, end);
        swap(data[begin], data[i]);
    }
    return sum;
}

这个 swap() 不建议使用 STL 里面的，建议自己写函数，当然最快的当然是使用宏 #define swap(a, b) {int t = a; a = b; b = t; }

如果原始数据不是 int ，而是一些比较大的类型（直接 swap() 比较慢），可以考虑上面讲的索引的方法，先把索引数组构造出来，然后再索引原始数据

跑了一遍测试 P1212P_{12}^{12}，速度差别比较明显（依次为三种方法）

1
2
3
4
5
6
sum = 479001600
14.138
sum = 479001600
27.141
sum = 479001600
5.653
原始代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define swap(a, b) \
    {              \
        int t = a; \
        a = b;     \
        b = t;     \
    }
using namespace std;
int a[1000], v[1000], n, k, sum;
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
void dfs(int cnt, int num)
{
    for (int i = 1; i <= n; i++) //组合 for(int i=num+1;i<=n;i++)
        if (!v[i])
        {
            a[cnt] = i;
            v[i] = 1;
            if (cnt == k)
            {
                sum++;
                // for (int i = 1; i <= k; i++)
                //     cout << a[i];
                // cout << endl;
            }
            else
                dfs(cnt + 1, i);
            v[i] = 0;
        }
}
int Perm(int begin, int end)
{
    if (begin == end) // 得到一个结果
        return 1;
    int sum = 0;
    for (int i = begin; i <= end; i++)
    {
        swap(data[begin], data[i]);
        sum += Perm(begin + 1, end);
        swap(data[begin], data[i]);
    }
    return sum;
}
int main()
{
    // cin >> n >> k;
    n = k = 12;

    clock_t start, end;

    start = clock();

    do
    {
        sum++;
    } while (next_permutation(data, data + 12));
    end = clock();
    cout << "sum = " << sum << endl;
    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;

    sort(data, data + 11);
    sum = 0;

    start = clock();
    dfs(1, 0);
    end = clock();
    cout << "sum = " << sum << endl;
    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;

    start = clock();
    sum = Perm(0, 11);
    end = clock();
    cout << "sum = " << sum << endl;
    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;

    return 0;
}

求 n 个元素中任意 m 个元素的全排列

next_permutation() 必然是不能用了，而我手搓的方法虽然可以解决，但是效率感人，还是不能用

对于最后一个方法，只需改一个地方就能很好地完成任务，把边界条件改一下即可

1
2
if (begin == m) // 得到一个结果（前 m 项就是结果）
    return 1;

组合

子集生成问题

组合问题，其实就是对某一个元素选或者不选的问题，这本质就是求子集问题

下面先来解决一个前置问题：如何枚举一个集合的所有子集

而其实这一问题可以轻松地使用二进制解决

譬如说，假如某个集合有 3 个元素：{A,B,C}，那么所有的子集就有 23=82^{3} = 8 种，可以使用下面对应的二进制数表示（0 表示不选，1 表示选）

子集 ∅ {A} {B} {A,B} {C} {A,C} {B,C} {A、B、C}
二进制 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
十进制 0 1 2 3 4 5 6 7

所以说，如果想表示出有 n 个元素的所有集合，只需要以下两步：

  • 枚举 00 到 2n−12^{n}-1 的每一个数
  • 解析里面的 0 和 1

第一步很简单，来个 for 即可

1
for (int i = 0; i < pow(2, n); i++)

或者优雅一点，使用位运算

1
for (int i = 0; i < (1 << n); i++)

而对于第二步，可以借助按位与（&）

比如对于 1 1 0 ，分别使用 0 0 1 、 0 1 0 、 1 0 0 来进行与运算，这样就能依次判断每一个位有没有 1

1
2
3
for (int j = 0; j < n; j++)
    if (i & (1 << j))
        ...

把这两步组合一下，就可以解决枚举子集问题

1
2
3
4
5
6
7
8
9
10
11
12
void print_subset(int n)
{
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
                cout << j << " ";
        }
        cout << endl;
    }
}

求 n 个元素中任意 m 个元素的全组合

解决了子集问题，那么求 CnmC_{n}^{m} 就方便了：本质就是仅选取元素个数为 mm 的子集，也就是限定 i 中的 1 的个数只有 mm 个

那么如何来数 1 的个数呢？最笨的方法还是使用按位与，然后数有多少个结果不为 0 的

1
2
3
4
5
6
7
8
9
10
11
int num = 0, kk = i;
while (kk)
{
    if (kk & 1)
        num++;
    kk >>= 1;
}
if (num == m)
{
    ... // 解析 i
}

但是还有更快的方法，使用一个神奇的操作：kk = kk & (kk - 1);

它的作用是从右向左依次删除其中的 1，每执行一次就删一个，所以只需要数一共删了几次就行

1
2
3
4
5
6
7
8
9
10
int num = 0, kk = i;
while (kk)
{
    kk = kk & (kk - 1);
    num++;
}
if (num == m)
{
    ... // 解析 i
}

结合一下，就是下面的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
void print_subset(int n, int m)
{
    for (int i = 0; i < (1 << n); i++)
    {
        int num = 0, kk = i;
        while (kk)
        {
            kk = kk & (kk - 1);
            num++;
        }
        if (num == m)
        {
            for (int j = 0; j < n; j++)
            {
                if (i & (1 << j))
                    cout << j << " ";
            }
            cout << endl;
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    print_subset(n, m);
    return 0;
}