枚举算法

62 阅读 0 评论 41 点赞

我是靠谱客的博主舒服小蝴蝶，最近开发中收集的这篇文章主要介绍枚举算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

指数枚举

所谓指数型枚举，实际上指的是子集枚举问题，通常有两种枚举方式。
①递归枚举

#include<bits/stdc++.h>
using namespace std;

int num[16];
vector<int> ans;
int n;
void dfs(int k){
    if(k==n+1){
        for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";cout<<endl;
        return;
    }
    //枚举到k个元素，我们有两种枚举方式，包含还是不包含
    dfs(k+1);
    ans.push_back(num[k]);
    dfs(k+1);
    ans.pop_back();
    return ;
}

int main(){
    for(int i=0;i<16;i++)num[i]=i;
    cin>>n;
    dfs(1);
    return 0;
}

②位运算枚举

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int state=(1<<n)-1;
    //这句循环是子集枚举的最为核心的要点，我们一定要理清思路逻辑。
    for(int i=state;i;i=(i-1)&state){
        for(int j=0;i>>j;j++){
            if((i>>j)&1)cout<<j+1<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    return 0;
}

重复元素的枚举
子集II

class Solution {
public:
    vector<vector<int>> result;
    vector<int> tmp;
    vector<int> num;
    int len;
    void DFS(int k){
        if(k>=len){
            return;
        }
        for(int i=k;i<len;i++){
            //与我的思路一致，但是枚举的策略相反，这个是从左到右分成两段，取左段
            //我的思路是从左到右分成两段，取右段。
            if(i>k&&num[i]==num[i-1])continue;
            tmp.push_back(num[i]);
            result.push_back(tmp);
            DFS(i+1);
            tmp.pop_back();
        }

        return ;
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        num=nums;
        len=num.size();
        DFS(0);
        result.push_back(tmp);
        return result;
    }
};

ACM版本

#include<bits/stdc++.h>
using namespace std;

int n;
int num[10];
vector<int> ans; 
bool vise[10];
void dfs(int k){
	if(k==n+1){
		for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";cout<<endl;
		return ;
	}
	//逻辑上应当还是子集每个元素是否选取的问题，
	//但是这里对选取的元素进行了定序，也即，当我们决定选取某个位置的元素时，
	//后面所有与该元素相同的元素我们应当也选取，否则任意。
	if(vise[k-1]&&num[k]==num[k-1]){
		vise[k]=true;
		ans.push_back(num[k]);
		dfs(k+1);
		ans.pop_back();
		vise[k]=false;
	}else{
		dfs(k+1);
		vise[k]=true;
		ans.push_back(num[k]);
		dfs(k+1);
		ans.pop_back();
		vise[k]=false;
	}
	return ;
}

int main(){
	memset(vise,false,sizeof(vise));
	cin>>n;
	num[0]=-1;
	for(int i=1;i<=n;i++)cin>>num[i];
	dfs(1);
	return 0;
}

排列型枚举

按字面意思理解即可，下面这个枚举方式所有序列并不是按照字典序升序排列的。

#include<bits/stdc++.h>
using namespace std;

int n;
int num[9];

void dfs(int k){
    if(k==n){
        for(int i=0;i<n;i++){
            cout<<num[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=k;i<n;i++){
        swap(num[i],num[k]);
        dfs(k+1);
        swap(num[i],num[k]);
    }
    return ;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)num[i]=i+1;
    dfs(0);
    return 0;
}

为了按照字典序升序枚举元素，这里我们使用一个数组来标记顺序。

#include<bits/stdc++.h>
using namespace std;

int n;
int num[10];
bool vise[10];

void dfs(int k){
    if(k==n+1){
        for(int i=1;i<=n;i++){
            cout<<num[i]<<" ";
        }
        cout<<endl;
        return;
    }
    //使用一个辅助数组来定序是一种非常巧妙地编程技巧，值得我们仔细揣摩
    //除了对于元素不相同的数组，对于元素相同的数组，我们也可以使用一个局部的位置数组，
    //来限制当前位置同一个元素的枚举次数只有一次。
    for(int i=1;i<=n;i++){
        //用一个全局的vise数组来定序
        if(vise[i])continue;
        vise[i]=true;
        num[k]=i;
        dfs(k+1);
        vise[i]=false;
    }
    return ;
}
int main(){
    memset(vise,false,sizeof(vise));
    cin>>n;
    dfs(1);
    return 0;
}

重复元素枚举方法

#include<bits/stdc++.h>
using namespace std;

int n;
int num[10];
bool vise[10];
int ans[10];

void dfs(int k){
    if(k==n+1){
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        return;
    }
    //使用一个辅助数组来定序是一种非常巧妙地编程技巧，值得我们仔细揣摩
    //除了对于元素不相同的数组，对于元素相同的数组，我们也可以使用一个局部的位置数组，
    //来限制当前位置同一个元素的枚举次数只有一次。
    bool tip[10];
    memset(tip,false,sizeof(tip));
    for(int i=1;i<=n;i++){
        //用一个全局的vise数组来定序
		//注意vise是对原始数组下标的标记，而不是对原来元素的标记 
		//注意vise标记的判断一定是先于tip的，否则tip会将该位置没有枚举的元素标记为true 
        //用一个局部tip数组来去重 
        if(tip[num[i]]||vise[i])continue;
        tip[num[i]]=true;
        vise[i]=true;
        ans[k]=num[i];
        dfs(k+1);
        vise[i]=false;
    }
    return ;
}
int main(){
    memset(vise,false,sizeof(vise));
    cin>>n;
    for(int i=1;i<=n;i++)cin>>num[i];
    dfs(1);
    return 0;
}

上述方法代表着枚举问题的一般规律，为了按照从小到大的顺序枚举出所有可能的排列组合，我们使用了一个vise标记数组来定序，也即我们每次都将当前位置可以选择的最小元素先进行枚举，当最小的枚举结束后，我们枚举次小的，这样保证了枚举出来的所有排列组合是单调递增的。
而对于如何去重，一种方法是使用set去重，这里我们使用更加优美的定序去重法，也即我们在每个枚举到的状态节点中，新建一个标记数组，用来标记枚举到当前状态时，当前位置某个元素是否已经枚举过，如果枚举过，那么相同的元素如果再次枚举，则可能发生重复的可能，所以同一个元素在某个状态下只能枚举一次。这个技巧对于指数型枚举和组合型枚举也是适用的。

组合型枚举

这个枚举实际上就是排列枚举的一半，我们只需要将终止条件进行稍微改变即可。
定序枚举即可。

#include<bits/stdc++.h>
using namespace std;

int n;
int d;
int num[26];

void dfs(int k,int start){
    if(k==d+1){
        for(int i=1;i<=d;i++){
            cout<<num[i]<<" ";
        }
        cout<<endl;
        return;
    }
    //注意不包含次序，所以我们只需要枚举单调同一种组合的一种次序即可
    for(int i=start;i<=n;i++){
        num[k]=i;
        dfs(k+1,i+1);
    }
    return ;
}
int main(){
    cin>>n>>d;
    dfs(1,1);
    return 0;
}

实际上我们还可以将数组排序后，按照子集枚举的方式进行枚举，区别在于，在这个问题中我们只保存那些长度为k的集合。

//方法二——可以按照指数型枚举快速实现；
#include<bits/stdc++.h>
using namespace std;
vector<int> ans;
int n,m;
int vise[26];
void DFS(int k){
    if(m==ans.size()){
        for(int i=0;i<m;i++)cout<<ans[i]<<" ";cout<<endl;
        return;
    }
    if(k>n)return;
    ans.push_back(k);
    DFS(k+1);
    ans.pop_back();
    DFS(k+1);
    return;
}
int main(){
    cin>>n>>m;
    memset(vise,0,sizeof(vise));
    DFS(1);
    return 0;
}