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

[Beckham]

用 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}的数组。

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

[jky]

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

[Beckham]

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

[menc]

问题是生成组合？

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

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

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

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

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

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

[Beckham]

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

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

[menc]

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

[williamscorn]

std::bitset

[Beckham]

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

[Beckham]

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

[vingz]

用递归

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]

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]

@vingc723 感谢回答！

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

再次谢过！

[vingz]

@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]

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

[vingz]

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

[Beckham]

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

[qinbingchen]

楼主可以用 bitmap 啊 ...

[Beckham]

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

[qinbingchen]

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


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

[Beckham]

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