请教各位大神一个算法问题：如何遍历 0-1 数组中的某些位？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2795 天前的主题，其中的信息可能已经有所发展或是发生改变。

用 c++计算一个模型，需要用一个 0-1 变量控制后面乘子的选择。想实现的功能如下：

首先读取一个初始的数组，数组的值只含有{0,1}，判断其中值为 1 的下标，对这些下标的位进行全排列的组合。

比如原始的数组是{0,0,1,1,0,1,0,1,1,0}，第 3,4,6,8,9 位的值为 1 ，则有 2^5 种组合，让 3,4,6,8,9 的值分别为 0 或 1 枚举 2^5 种组合，并且输出这些数组，或者直接让这些数组作为乘子来求解模型。

生成如{0,0,1,0,0,1,0,0,1,0}，{0,0,0,0,0,1,0,1,1,0}的数组。

希望各位大神能够指点迷津，在此谢过！

第 1 条附言 · 2017-03-29 22:24:40 +08:00

感谢 @ vingc723 ，最后的代码已经测试通过，解决了我的燃眉之急。同时也感谢 @jky @menc @williamscorn ，你们的回复都让我开阔了视野，同样的问题也可以有这么多的思路。虽然我现在的知识储备还很有限，即使看起来这么简单的问题，我也还不能按照你们的建议一一实现这些方法。但是相信也能为以后有需要的人提供了有用的帮助。

还有我想请问最后的代码这种递归思维要怎么去考虑？感觉非常的简洁有效。

一直很喜欢 v2 的氛围，希望能一直保持下去！

再次谢谢各位！

乘子

下标

大神

组合

19 条回复 • 2017-05-06 21:08:29 +08:00

jky

2017-03-29 16:35:49 +08:00 via Android

找出所有 1 的下标，然后一个 for i = 0..1<<n ，用 i 的 1 到 n 位的值替换对应数组的值，这样应该就可以了吧。

Beckham

2017-03-29 16:53:18 +08:00

@jky 就是假设有 n 个为 1 的下标，分别对这些下标进行从 1 到 n 的左移运算吗？

menc

2017-03-29 16:54:14 +08:00

问题是生成组合？

有一个简单的方式来生成 n 位数的 0-1 的组合，就是：
输出 0 ~ 2^n-1 的二进制，就是 n 位数的 0-1 的组合。

------
问题是怎么做才搞笑？
如果不稀疏，就这么存这么算吧。

如果足够稀疏，而且维度比较大，数据比较多，那么要考虑：
关键字“稀疏矩阵的表示”，来压缩内存消耗。

对于单独的乘法运算，是不需要一个数组一个数组来点乘的，以你的例子为例， 32 个数组， 10 维特征，是可以把 2^5=32 种组合合并成 32 * 10 的矩阵，与 10 * 1 的后面的乘子做矩阵乘法，直接得到 32 * 1 的结果，为什么这样的，因为矩阵乘法有一些优化速度的 trick 。

对于稀疏矩阵，则额外有稀疏矩阵的乘法实现 trick 。

搜索“矩阵乘法”“矩阵乘法优化”“稀疏矩阵乘法”。
可得。

Beckham

2017-03-29 17:10:38 +08:00

@menc 非常感谢您的回复！输出 0~2^n-1 的二进制，要如何只对某些下标操作而不影响数组其他位？

暂时的数据可能最多就是 2^10=1024 种组合，可能以后也就扩展到 2^20=1048576 ，这么多维的数组是不是就非常占用空间了？

menc

2017-03-29 17:28:38 +08:00

搞一个 0,1,2,3,4 -> 3,4,6,8,9 的 mapping 就好了啊

williamscorn

2017-03-29 18:13:33 +08:00

std::bitset

Beckham

2017-03-29 18:45:39 +08:00

@menc 还没要怎么 map ，能烦请写个范例吗 T_T 谢谢！

Beckham

2017-03-29 18:46:34 +08:00

@williamscorn 看了一下 bitset 按位操作好像非常方便，想请问要怎么实现遍历的组合操作呢？

vingz

2017-03-29 20:34:29 +08:00

用递归

fun()
{
1. end case 如果遇到 item 越界打印当前数组
2. 找到从当前 item 开始的下一个 1
3. item+1 call fun()
4. 设置该位为 0 ， item+1 call fun()
}

item 为开始搜索的索引位置
每次搜到一个 1 之后，该位有 1 和 0 两种组合，分别调用本函数递归；
时间复杂度为 O(n);空间复杂度为 O(2^e),e 为 1 的个数;

vingz

2017-03-29 20:39:23 +08:00

void fun( int a[], int begin, int end )
{
int i;

for( i = begin; i < end; i++ )
{
if( a[i] == 1 )
{
fun( a, begin+1, end );
a[i] = 0;
fun( a, begin+1, end );
break;
}
}

if( i == end )
{
//print array
}
}

Beckham

2017-03-29 21:45:11 +08:00

@vingc723 感谢回答！

我尝试了一下问题中的例子，输出的结果只有 10 组，并且只能把 1 变为 0 ，不能反向，到后面的结果开始出现重复的数组。能否邮件联系？我的邮箱是 YmVja2hhbXZ3YW5nQGdtYWlsLmNvbQ==

再次谢过！

vingz

2017-03-29 22:07:14 +08:00

@Beckham 收一下邮件吧
新函数如下
<code>
void fun( int a[], int begin, int end )
{
int i;

for( i = begin; i < end; i++ )
{
if( a[i] == 1 )
{
fun( a, i+1, end );
a[i] = 0;
fun( a, i+1, end );
a[i] = 1;//restore
break;
}
}

if( i == end )
{
//print array
for( i = 0; i < end; i++ )
{
printf( "%d ", a[i] );
}
printf( "\n" );
}
}
</code>

Beckham

2017-03-29 22:26:04 +08:00

@vingc723 刚才还在调试原来的代码，心想这么晚了应该到第二天才有回信，还想说自己试着解决。看到回信真的非常惊喜，感谢！

vingz

2017-03-29 22:28:26 +08:00

@Beckham 不客气，我写第一份代码主要是想帮你理解思路，所以我本身没有测试那份代码，不小心误导你了。

Beckham

2017-03-30 08:31:44 +08:00

@vingc723 能给出代码已经非常感激。主要是能力不足又没能调试出来。要多加学习才行。

qinbingchen

2017-05-05 21:38:18 +08:00

楼主可以用 bitmap 啊 ...

Beckham

2017-05-05 22:08:21 +08:00

@qinbingchen 之前也看过一些介绍，但由于水平实在有限，具体的算法还没有研究出来。不知道朋友你是否有写过类似的算法的经验？

qinbingchen

2017-05-05 23:41:28 +08:00

@Beckham 额 ...我是个渣渣...上面那位的递归能用的话,,,如果你以后数据变大了,数组太浪费空间的话..你就用 bitmap 位操作的,,,控制好就行这样数据应该是够你存的了递归改成迭代应该就好了 .... 如果结果飙升到几百万组,就这么办吧..

优化就是只遍历一次数组.用 hashmap 存着,,,这样就知道 1 的位置...迭代 hash map 操作 bitmap 位就行了
渣渣只能帮你到这了

Beckham

2017-05-06 21:08:29 +08:00

@qinbingchen 渣渣在此。谢谢提供这么好的建议，等到我增加了难度我就去学习学习，如果有成功的案例再反馈回来~谢谢~