用 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
jky 2017-03-29 16:35:49 +08:00 via Android 1
找出所有 1 的下标,然后一个 for i = 0..1<<n ,用 i 的 1 到 n 位的值替换对应数组的值,这样应该就可以了吧。
|
3
menc 2017-03-29 16:54:14 +08:00 1
问题是生成组合?
有一个简单的方式来生成 n 位数的 0-1 的组合,就是: 输出 0 ~ 2^n-1 的二进制,就是 n 位数的 0-1 的组合。 ------ 问题是怎么做才搞笑? 如果不稀疏,就这么存这么算吧。 如果足够稀疏,而且维度比较大,数据比较多,那么要考虑: 关键字“稀疏矩阵的表示”,来压缩内存消耗。 对于单独的乘法运算,是不需要一个数组一个数组来点乘的,以你的例子为例, 32 个数组, 10 维特征,是可以把 2^5=32 种组合合并成 32 * 10 的 矩阵,与 10 * 1 的后面的乘子做矩阵乘法,直接得到 32 * 1 的结果,为什么这样的,因为矩阵乘法有一些优化速度的 trick 。 对于稀疏矩阵,则额外有稀疏矩阵的乘法实现 trick 。 搜索“矩阵乘法”“矩阵乘法优化”“稀疏矩阵乘法”。 可得。 |
4
Beckham OP @menc 非常感谢您的回复!输出 0~2^n-1 的二进制,要如何只对某些下标操作而不影响数组其他位?
暂时的数据可能最多就是 2^10=1024 种组合,可能以后也就扩展到 2^20=1048576 ,这么多维的数组是不是就非常占用空间了? |
5
menc 2017-03-29 17:28:38 +08:00
搞一个 0,1,2,3,4 -> 3,4,6,8,9 的 mapping 就好了啊
|
6
williamscorn 2017-03-29 18:13:33 +08:00 1
std::bitset
|
8
Beckham OP @williamscorn 看了一下 bitset 按位操作好像非常方便,想请问要怎么实现遍历的组合操作呢?
|
9
vingz 2017-03-29 20:34:29 +08:00 2
用递归
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 的个数; |
10
vingz 2017-03-29 20:39:23 +08:00 2
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 } } |
11
Beckham OP @vingc723 感谢回答!
我尝试了一下问题中的例子,输出的结果只有 10 组,并且只能把 1 变为 0 ,不能反向,到后面的结果开始出现重复的数组。能否邮件联系?我的邮箱是 YmVja2hhbXZ3YW5nQGdtYWlsLmNvbQ== 再次谢过! |
12
vingz 2017-03-29 22:07:14 +08:00 1
@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> |
13
Beckham OP @vingc723 刚才还在调试原来的代码,心想这么晚了应该到第二天才有回信,还想说自己试着解决。看到回信真的非常惊喜,感谢!
|
16
qinbingchen 2017-05-05 21:38:18 +08:00
楼主可以用 bitmap 啊 ...
|
17
Beckham OP @qinbingchen 之前也看过一些介绍,但由于水平实在有限,具体的算法还没有研究出来。不知道朋友你是否有写过类似的算法的经验?
|
18
qinbingchen 2017-05-05 23:41:28 +08:00 1
@Beckham 额 ...我是个渣渣...上面那位的递归能用的话,,,如果你以后数据变大了,数组太浪费空间的话..你就用 bitmap 位操作的,,,控制好就行 这样数据应该是够你存的了 递归改成迭代应该就好了 .... 如果结果飙升到几百万组,就这么办吧..
优化就是只遍历一次数组.用 hashmap 存着,,,这样就知道 1 的位置...迭代 hash map 操作 bitmap 位就行了 渣渣只能帮你到这了 |
19
Beckham OP @qinbingchen 渣渣在此。谢谢提供这么好的建议,等到我增加了难度我就去学习学习,如果有成功的案例再反馈回来~谢谢~
|