生成排列与生成子集

排列或子集的生成，可以使用递归构造，也可以直接生成。直接生成的方法时间复杂度高，无法进行适当的剪枝，如果想减小时间复杂度，可以使用回溯法进行递归构造。

1、排列的递归构造很简单，伪码如下：

print_permutation(序列R，集合S)
	if(S为空)
        print 序列R
        return
	for s in 集合S
        print_permutation(序列R + s, 集合S - s)

该伪码假设集合S中的元素不重复，如果需要生成可重集的排列，则需要在循环中对集合S中每个“不同元素”进行“该元素在R中出现的次数小于在S中出现的次数”的判断。

2、排列的直接生成可以使用STL中的next_permutation()，示例代码如下：

#include <iostream>
#include <algorithm>

int main() {
	//test1
	int myints[] = {1, 2, 3};
	std::sort(myints, myints + 3);
	std::cout << "The 3! possible permutations with 3 elements:
";
    do {
    	std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '
';
    } while(std::next_permutation(myints, myints + 3));
    std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '
';
    
	//test2
	std::string s = "aba";
	std::sort(s.begin(), s.end());
	do {
	    std::cout << s << '
';
	} while(std::next_permutation(s.begin(), s.end()));

    return 0;
}

3、子集的生成可以使用位向量法，递归方式，参考代码如下：

#include <cstdio>
#include <vector>
using namespace std;

void print_subset(vector<int> &R, vector<int> &S, int index) {
    if(index == R.size()) {
        for(int i = 0; i < S.size(); i++)
            if(S[i]) printf("%d ", R[i]);
        printf("
");
        return;
    }
    S[index] = 0;
    print_subset(R, S, index + 1);
    S[index] = 1;
    print_subset(R, S, index + 1);
}

int main() {
    vector<int> R{1,2, 3};
    vector<int> S(R.size(), 0);
    print_subset(R, S, 0);

    return 0;
}

4、子集的直接生成可以使用二进制法，参考代码如下：

void print_subset(vector<int> &S) {
    for(int i = 0; i < (1 << S.size()); i++) {
        for(int j = 0; j < S.size(); j++) {
            if(i & (1 << j)) printf("%d ", S[j]);
        }
        printf("
");
    }
}

此方法虽然简洁，但要求集合S的元素不超过int的位数。

生成排列与生成子集

相关推荐