2018-03-12

序列的全排列、子集的生成

之所以要生成这样的排列，是为了判断每一种解答的可能，从而从所有的解答中搜寻想要的答案。

序列的全排列：
最终的目的是生成有重复元素的全排列的解答空间
子集的生成:
仅仅是0~n-1子集合的生成

序列的全排列

生成1~n的排列

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
int n;
int num[maxn];
void print_permutation(int n, int cur){
    if(cur == n){
        for(int i=0; i<n; i++){
            printf("%d ", num[i]);
        }
        printf("\n");
        return;
    }
    for(int i=1; i<=n; i++){
        bool ok = true;
        for(int j=0; j<cur; j++){
            if(num[j] == i) ok = false;
        }
        if(ok){
            num[cur] = i;
            print_permutation(n, cur+1);
        }
    }
}
int main()
{
    int n;
    n = 3;
    print_permutation(3, 0);
    return 0;
}

可重复元素的全排列

num[]要事先排好序！！！

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int num[maxn];
int temp[maxn];
int n;
void print_permutation(int cur){
    if(cur == n){
        for(int i=0; i<n; i++){
            printf("%d ", temp[i]);
        }
        printf("\n");
        return ;
    }
    for(int i=0; i<n; i++){
        if(i==0||num[i]!=num[i-1]){
            int c1, c2;
            c1 = c2 = 0;
            for(int j=0; j<cur; j++)if(num[i] == temp[j]) c1++;
            for(int j=0; j<n; j++) if(num[j] == num[i]) c2++;
            if(i!=0||num[i]!=num[i-1]){
                if(c1<c2){
                    temp[cur] = num[i];
                    print_permutation(cur+1);
                }
            }
        }
    }
    return ;
}
int main(){
    cin>>n;
    for(int i=0; i<n; i++) cin>>num[i];
    sort(num, num+n);//必须要先排好序
    print_permutation(0);
    return 0;
}

使用系统的函数:next_permutation

注意打印的数组要先排好序！！！

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    n = 3;
    int num[5];
    num[0] = 1;
    num[1] = 2;
    num[2] = 2;
    do{
        for(int i=0; i<n; i++)printf("%d ", num[i]);
        printf("\n");
    }while(next_permutation(num, num+n));
    return 0;
}

子集的生成

增量构造法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
void print_subset(int n, int *A, int cur){
    for(int i=0; i<cur; i++){
        printf("%d ", A[i]);
    }
    printf("\n");
    int s = cur?A[cur-1]+1:0;
    for(int i=s; i<n; i++){//运用了定序的技巧，避免了重复枚举
        A[cur] = i;
        print_subset(n, A, cur+1);
    }
    return ;
}
int num[maxn];
int main()
{
    print_subset(3, num, 0);
    return 0;
}

位向量法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
int num[maxn];
bool vis[maxn];
void print_subset(int n, bool *vis, int *num, int cur){
    if(cur == n){
        for(int i=0; i<n; i++){
            if(vis[i]) printf("%d ", num[i]);
        }
        printf("\n");
        return ;
    }
    vis[cur] = true;
    print_subset(n, vis, num, cur+1);
    vis[cur] = false;
    print_subset(n, vis, num, cur+1);
}
int main(){
    num[0] = 2;
    num[1] = 3;
    num[2] = 1;
    memset(vis, 0, sizeof(vis));
    print_subset(3, vis, num, 0);
    return 0;
}

二进制法

比较好理解，而且容易书写

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
void print_subset(int n ,int s){
    for(int i=0; i<n; i++){
        if(s&(1<<i))printf("%d ", i);
    }
    printf("\n");
}
int main(){
    int n=3;
    for(int i=0; i<(1<<n); i++){
        print_subset(n, i);
    }
    return 0;
}

未解决的问题

本文标题:序列的全排列、子集的生成

文章作者:Babydragon

发布时间:2018-03-12, 16:19:39

最后更新:2018-03-23, 13:31:11

原始链接:http://baolintian.github.io/2018/03/12/子集生成/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。