Fork me on GitHub

排列组合问题

发表于 | 分类于 | | 本文总阅读量 次
本文给出了n个不同元素的全排列和全组合的求解方案。

1. 排列组合问题

1.1. 全排列

全排列就是有 $n$ 个不同的元素，求所有元素的所有排列。比如 $a,\;b,\;c$ 的所有排列为 ${abc},\;{acb},\;{bac},\;{bca},\;{cab},\;{cba}$。$n$ 个元素的排列个数是 $n!$。

1.1.1. 全排列

举例：$a,\;b,\;c$ 的全排列为 ${abc},\;{acb},\;{bac},\;{bca},\;{cab},\;{cba}$。

思路：取集合中的任意一个元素与第一个数字交换，然后将除第一个元素外的后面所有的元素全排列；依次类推。更广泛的，假设前 $m$ 个元素已经排好，将剩下 $n-m$ 个元素全排，就得到了在前 $m$ 个元素已经排好的情况下的全排。用递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
void permutatons(vector<T> &vec, int k, int m){
    if(k == m){             // 递归基础部分
        for(int i = 0; i < vec.size(); ++i){
            cout << vec[i];
        }
        cout << endl;
    }else{
        for(int i = k; i <= m; ++i){
            swap(vec[k], vec[i]);
            permutatons(vec, k + 1, m);
            swap(vec[k], vec[i]);       // 交换，还原数组元素
        }
    }
}

1.1.2. 去重全排列

举例：$a,\;b,\;b$ 的去重全排列为 ${abb},\;{bab},\;{bba}$。

思路：去重全排列就是从要全排的第一个元素分别与它后面每个非重复出现的元素交换。

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
template<typename T>
bool IsSwap(vector<T> &vec, int k, int m){
    for(; k < m; ++k){
        if(vec[k] == vec[m])
            return false;
    }
    return true;
}

template<typename T>
void permutatons(vector<T> &vec, int k, int m){
    if(k == m){
        for(int i = 0; i < vec.size(); ++i){
            cout << vec[i];
        }
        cout << endl;
    }else{
        for(int i = k; i <= m; ++i){
            if (IsSwap(vec, k, i)){
                swap(vec[k], vec[i]);
                permutatons(vec, k + 1, m);
                swap(vec[k], vec[i]);
            }
        }
    }
}

1.2. 全组合

举例：$a,\;b,\;c$ 的全组合为 ${a},\;{b},\;{c},\;{ab},\;{ac},\;{bc},\;{abc}$。

思路：假设有 $n$ 个元素，则共有 $2^n-1$ 种组合。借用位操作，1 表示取该元素，0 表示不取该元素。假设有 $a,\;b,\;c$ 三个元素，则取 $a$ 为 $100$，$ab$ 是 $110$，而 $000$ 没有意义。所以解决方案就是循环 $1$ 至 $2^n-1$，然后输出对应代表的组合即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
void combination(vector<T> &vec){
    if(vec.size() == 0)
        return;
    int len = vec.size();
    int n = 1 << len;
    for(int i = 1; i < n; ++i){        // 从 1 循环到 2^len-1
        for(int j = 0; j < len; ++j){
            if(i & (1 << j)){       // 判断第j位是否为1
                cout << vec[j];
            }
        }
        cout << endl;
    }
}