V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Beckham
V2EX  ›  C

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

  •  
  •   Beckham · 2017-03-29 16:23:11 +08:00 · 2319 次点击
    这是一个创建于 2787 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用 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
        1
    jky  
       2017-03-29 16:35:49 +08:00 via Android   ❤️ 1
    找出所有 1 的下标,然后一个 for i = 0..1<<n ,用 i 的 1 到 n 位的值替换对应数组的值,这样应该就可以了吧。
    Beckham
        2
    Beckham  
    OP
       2017-03-29 16:53:18 +08:00
    @jky 就是假设有 n 个为 1 的下标,分别对这些下标进行从 1 到 n 的左移运算吗?
    menc
        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 。

    搜索“矩阵乘法”“矩阵乘法优化”“稀疏矩阵乘法”。
    可得。
    Beckham
        4
    Beckham  
    OP
       2017-03-29 17:10:38 +08:00
    @menc 非常感谢您的回复!输出 0~2^n-1 的二进制,要如何只对某些下标操作而不影响数组其他位?

    暂时的数据可能最多就是 2^10=1024 种组合,可能以后也就扩展到 2^20=1048576 ,这么多维的数组是不是就非常占用空间了?
    menc
        5
    menc  
       2017-03-29 17:28:38 +08:00
    搞一个 0,1,2,3,4 -> 3,4,6,8,9 的 mapping 就好了啊
    williamscorn
        6
    williamscorn  
       2017-03-29 18:13:33 +08:00   ❤️ 1
    std::bitset
    Beckham
        7
    Beckham  
    OP
       2017-03-29 18:45:39 +08:00
    @menc 还没要怎么 map ,能烦请写个范例吗 T_T 谢谢!
    Beckham
        8
    Beckham  
    OP
       2017-03-29 18:46:34 +08:00
    @williamscorn 看了一下 bitset 按位操作好像非常方便,想请问要怎么实现遍历的组合操作呢?
    vingz
        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 的个数;
    vingz
        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
    }
    }
    Beckham
        11
    Beckham  
    OP
       2017-03-29 21:45:11 +08:00
    @vingc723 感谢回答!

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

    再次谢过!
    vingz
        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>
    Beckham
        13
    Beckham  
    OP
       2017-03-29 22:26:04 +08:00
    @vingc723 刚才还在调试原来的代码,心想这么晚了应该到第二天才有回信,还想说自己试着解决。看到回信真的非常惊喜,感谢!
    vingz
        14
    vingz  
       2017-03-29 22:28:26 +08:00
    @Beckham 不客气,我写第一份代码主要是想帮你理解思路,所以我本身没有测试那份代码,不小心误导你了。
    Beckham
        15
    Beckham  
    OP
       2017-03-30 08:31:44 +08:00
    @vingc723 能给出代码已经非常感激。主要是能力不足又没能调试出来。要多加学习才行。
    qinbingchen
        16
    qinbingchen  
       2017-05-05 21:38:18 +08:00
    楼主可以用 bitmap 啊 ...
    Beckham
        17
    Beckham  
    OP
       2017-05-05 22:08:21 +08:00
    @qinbingchen 之前也看过一些介绍,但由于水平实在有限,具体的算法还没有研究出来。不知道朋友你是否有写过类似的算法的经验?
    qinbingchen
        18
    qinbingchen  
       2017-05-05 23:41:28 +08:00   ❤️ 1
    @Beckham 额 ...我是个渣渣...上面那位的递归能用的话,,,如果你以后数据变大了,数组太浪费空间的话..你就用 bitmap 位操作的,,,控制好就行 这样数据应该是够你存的了 递归改成迭代应该就好了 .... 如果结果飙升到几百万组,就这么办吧..


    优化就是只遍历一次数组.用 hashmap 存着,,,这样就知道 1 的位置...迭代 hash map 操作 bitmap 位就行了
    渣渣只能帮你到这了
    Beckham
        19
    Beckham  
    OP
       2017-05-06 21:08:29 +08:00
    @qinbingchen 渣渣在此。谢谢提供这么好的建议,等到我增加了难度我就去学习学习,如果有成功的案例再反馈回来~谢谢~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2630 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 15:52 · PVG 23:52 · LAX 07:52 · JFK 10:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.