#4.排列与组合

2017-07-30

排列组合是高中数学里我们学过的知识，不过那时候我们计算的是满足某一条件的排列组合的总数，也就是说，我们求的是一个数值。而今天的问题是：通过完成一个程序，列出某个排列组合的所有可能情况。

问题：

  1. 如何生成由$n$个数字组成的所有$k$位数?
  2. 如何生成$n$个数中选择$k$个数的所有排列$A_n^k$ ?
  3. 如何生成$n$个数中选择$k$个数的所有组合$C_n^k$ ?

关键点：

  1. 填每一位时，把选择的数字存到一个结果数组中，填完所有位之后一起输出。
  2. 填完一位之后要选择下一种情况时，需要把当前元素从结果数组ary[]中弹出。
  3. 排列，组合不能重复使用元素，因此用过的要做个标记（-1）。
  4. 组合与顺序无关，默认采用递增的顺序。

代码：
求$N_5^4, A_5^4$和$C_5^4$：

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
77
78
79
80
81
82
83
84
85
86
87
88
//
// Created by Amy on 2017/7/29.
//
/*Arrangement and Combination*/
#include <iostream>
#include <vector>
using namespace std;
vector<int> ary;
vector<int> eles = {1, 2, 3, 4, 5};
int n_ = eles.size(); // numbers for chosen
int k_ = 4; // bits num
/*List Number*/
void N(int k) {
    if (k == 0) {
        for (int e : ary) {
            cout << e << " ";
        }
        cout << endl;
    } else {
        for (int e : eles) {
            ary.push_back(e);
            N(k - 1);
            ary.pop_back();
        }
    }
}
/*Arrangement*/
void A(int k) {
    if (k == 0) {
        for (int e : ary) {
            cout << e << " ";
        }
        cout << endl;
    } else {
        for (int i = 0; i < n_; i++) {
            if (eles[i] > 0) {
                ary.push_back(eles[i]);
                int temp = eles[i];
                eles[i] = -1;
                A(k - 1);
                eles[i] = temp;
                ary.pop_back();
            }
        }
    }
}
/*Combination*/
void C(int k) {
    if (k == 0) {
        for (int e : ary) {
            cout << e << " ";
        }
        cout << endl;
    } else {
        int last_used_idx = 0;
        for (last_used_idx = n_ - 1; last_used_idx >= 0 && eles[last_used_idx] > 0; last_used_idx--);
        if (k == n_ - last_used_idx) {
            for (int i = 0; i < n_; i++) {
                if (eles[i] > 0) {
                    ary.push_back(eles[i]);
                }
            }
        } else {
            for (int j = last_used_idx + 1; j <= n_ - k; j++) {
                ary.push_back(eles[j]);
                int temp = eles[j];
                eles[j] = -1;
                C(k - 1);
                eles[j] = temp;
                ary.pop_back();
            }
        }
    }
}
int main() {
    cout << "The numbers are: " << endl;
    N(k_);
    cout << "The arrangement is: " << endl;
    A(k_);
    cout << "The combination is: " << endl;
    C(k_);
}

运行结果：

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
The numbers are:
1 1 1 1
1 1 1 2
1 1 1 3
1 1 1 4
1 1 1 5
1 1 2 1
... ...
5 5 5 1
5 5 5 2
5 5 5 3
5 5 5 4
5 5 5 5
The arrangement is:
1 2 3 4
1 2 3 5
1 2 4 3
1 2 4 5
... ...
5 4 2 1
5 4 2 3
5 4 3 1
5 4 3 2
The combination is:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5