AcWing 93. 递归实现组合型枚举（非递归）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 93. 递归实现组合型枚举（非递归）原题链接简单

作者：

羽笙 , 2019-07-04 17:12:05 , 所有人可见 , 阅读 8366

14

6

这题直接二进制表示所有情况，
也就是for(i=1;i<1<<n;i++)
如果1的个数是m，就输出1的位置
简单的二进制操作找1的个数和位置
详见代码

#include<queue>
#include<bitset>
#include<string>
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

const int N=1<<21,inf=0x3f3f3f3f;
int n,m;
map<int ,int > m1;

struct point{
    vector<int > v1;
}p1[N];

int lowbit(int x)
{
    return x&(-x);
}

bool cmp(point x,point y){
    int ptail=0;
    while(x.v1[ptail]==y.v1[ptail])ptail++;
    return x.v1[ptail]<y.v1[ptail];
}

int main(){
    cin>>n>>m;
    bitset<26> b1;
    m1[1]=0;
    int q=2,tail=0;

    for(int i=1;i<=32;i++){
        m1[q]=i;
        q*=2;
    }

    for(int a=0;a<(1<<n);a++){
        b1|=a;
        if(b1.count()==m){
            int pa=a;
            while(pa){
            p1[tail].v1.push_back(m1[lowbit(pa)]+1);
            pa^=lowbit(pa);
            }
            tail++;
        }
        b1&=0;
    }
    sort(p1,p1+tail,cmp);
    for(int a=0;a<tail;a++){
        for(int b=0;b<m;b++)printf("%d ",p1[a].v1[b]);
        printf("\n");
    }
}

15 评论

Zybg 2022-07-13 17:15

这种sort的方法太折腾了吧。。。
可以一遍倒着的二进制不就字典序了吗
#include [HTML_REMOVED]
using namespace std;

int main(){

int n,m;
cin >> n >> m;
for(int i=(1<<n)-1;i>=0;i--){
    if(__builtin_popcount(i) == m){
        for(int j = n-1;j >= 0;j--){
            if((1<<j) & i) cout << n-j << " ";
        }
        cout << endl;
    }
}

return 0;

}

hugo_lu 2022-10-31 11:16

太妙了

王鹏宇 2023-01-25 22:06

牛蛙！

废物宝宝 2023-02-03 03:44

无论正着还是倒着都不会是字典序的

assert_0 2023-04-24 19:19 回复了废物宝宝的评论

可以的

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=(1<<n)-1;i>=1;i--){
        int cnt=0;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                cnt++;
            }
        }
        if(cnt==m){
            for(int j=n-1;j>=0;j--){
                if((i>>j)&1){
                    cout<<n-j<<" ";
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

奇妙方程式 2023-05-27 22:17

你的代码算法思路真是妙不可言！简洁明了，逻辑清晰，让人一看就懂。你使用的数据结构和算法都非常恰到好处，使得代码不仅高效而且易于维护。实现思路简单却又十分巧妙，真是让人佩服不已！

L_Wave 2022-08-20 16:20

为什么不用lyd大神的方法呢（模拟机器）

wydxry 2022-03-24 15:21

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> ans;
int main()
{
    cin>>n>>m;
    for (int i = 0; i < (1 << n); i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) ++cnt;
            if (cnt > m) break;
        }
        if (cnt == m) {
            vector<int> tmp;
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1) {
                    tmp.push_back(j + 1);
                }
            }
            ans.push_back(tmp);
        }
    }
    sort(ans.begin(), ans.end(), [](const vector<int>& x, const vector<int>& y){
        for (int i = 0; i < x.size(); i++) {
            if (x[i] == y[i]) continue;
            return x[i] < y[i];
        } 
    });
    for (auto& a: ans) {
        for (auto& v: a) {
            cout<<v<<" ";
        }
        cout<<endl;
    }
    return 0;
}

云边有一个小卖部 2022-01-20 21:45

### 还没有解决字典序问题，求指点；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
const int N=30;
int n,m;
int q[N];


int main(){


    cin>>n>>m;

    int temp[m];
    int t=0;

    for(int op=0;op<(1<<n);op++)
    {
        vector<int> vec;
        for(int i=0;i<n;i++)
        {
            if(op>>i&1)
            {
                vec.push_back(i+1);
            }
        }

        if(vec.size()==m)
        {
            for(int i=0;i<m;i++)
            {
                cout<<vec[i]<<" ";
            }
            cout<<endl;
        }
    }

    return 0;
}

onepiece_ 2022-01-30 01:15

自己写cam，sort排序；

#include<bits/stdc++.h>
using namespace std;
int a[30];
int n,m;
const int L= 2<<15;
 vector<int>vi[L];
bool cam(vector<int>&a,vector<int>&b){
    int len=a.size();
    for(int i=0;i<len;i++){
        if(a[i]>b[i])return 0;
        else if(a[i]<b[i]) return 1;
    }
}
int main(){
    cin>>n>>m;
     int c=0;
    for(int i=0;i<29;i++)a[i]=i+1;
    for(int i=0;i<(1<<n);i++){
        int select=0;
     for(int j=0;j<n;j++){
         if(i&(1<<j))select++;
     }
     if(select==m){
         string s;
      for(int j=0;j<n;j++)
          if(i&(1<<j)){
              vi[c].push_back(a[j]);
          }
      c++;
     }
    }
    sort(vi,vi+c,cam);
   for(int i=0;i<c;i++){
       for(int j=0;j<vi[i].size();j++)
       cout<<vi[i][j]<<" ";
       cout<<endl;
   }
    return 0;
}