【求助】怎么快速找到n位二进制中m个1的所有组合情况，非暴力

a5530860

2019/9/27镜像同步12 回复

如题，例如8位二进制，找出3个1的所有组合。

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

abcbing机器人#1 · 2019/9/27

zhxiao机器人#2 · 2019/9/27

能再详细描述一下问题吗？

a5530860机器人#3 · 2019/9/27

比如8位中只有一个1，则有8种情况，00000001，00000010等等。固定长度和固定1的个数，快去得到所有组合情况。【在 zhxiao (zxiao) 的大作中提到: 】 : 能再详细描述一下问题吗？

a5530860机器人#4 · 2019/9/27

转移方程该是怎样的呢，好像也挺麻烦的。[ema1] 【在 abcbing (hellobupt) 的大作中提到: 】 : dp

boke1208机器人#5 · 2019/9/27

c(n,m)吗。。。ps这回答和骂人一样

a5530860机器人#6 · 2019/9/27

情况个数是这样，但是想快速得到这些序列。【在 boke1208 (福莱||纸鹅的小弟) 的大作中提到: 】 : c(n,m)吗。。。ps这回答和骂人一样

ytz123机器人#7 · 2019/9/27

如果需要所有方案就爆搜，如果只需要方案数就用组合数来算

ytz123机器人#8 · 2019/9/27

考虑爆搜的时候，某种情况的终止条件就是前面已经处理的位上已经填了m个1，这时后面都填0，然后把这种方案存下来就可以。考虑一下递归过程，复杂度应该是接近O(方案数*n)的

lanvent机器人#9 · 2019/9/27

n位选k的子集。ref:挑战程序设计竞赛 int comb = (1<<k) - 1; while(comb < 1<<n) { //在这里进行针对组合的处理 int x = comb & -comb, y = comb + x; comb = ((comb & -y) / x >> 1) | y; }