V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
lbfeng
V2EX  ›  问与答

解一道算法题

  •  
  •   lbfeng · 2015-12-09 04:15:25 +08:00 · 2012 次点击
    这是一个创建于 3279 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有 A, B, C, D, E, F 这几项。还有(A, B), (B, E), (E, F), (A, C), (A, B, F)...
    要求找出包含 A-F 所有项的集合。比如[(A, B), (C, D), (E, F)]。

    我可以找出所有包含 A 的(A, B), (A, C)..., 所有包含 B 的(A, B), (B, C)...以此类推,再求他们的交集???复杂度是多少?这个解法看起来不像最优解。有别的招吗?

    6 条回复    2015-12-09 13:22:03 +08:00
    statm
        1
    statm  
       2015-12-09 04:23:01 +08:00
    LZ 可以去搜搜 BFS 算法
    ruandao
        2
    ruandao  
       2015-12-09 07:36:07 +08:00
    是求全排列吗?
    messyidea
        3
    messyidea  
       2015-12-09 08:26:49 +08:00 via Android
    是不是只有 A 到 F 6 项,里面元素可以重复吗。比如
    (a , b)和(a , c),可以先找出所有项,每一项用状态压缩把他们压成一个数字,然后搜索起来方便一点,只需要&操作,然后看结果是否等于(11111)[二进制]就可以了
    liberize
        4
    liberize  
       2015-12-09 12:37:28 +08:00
    贴一个可行的解法,应该可以优化:

    #include <iostream>

    using namespace std;

    const char *data[] = {"AB", "C", "ACF", "BE", "EF", "D", "AC", "CD", "ABF"};
    int size = sizeof(data) / sizeof(char *);


    void find(int start, int *selected, int step, unsigned status)
    {
    for (int index = start; index < size; index++) {
    const char *item = data[index], *first;
    // 检测是否现有的选择冲突(即有重复的项)
    for (first = item; *first != '\0'; first++) {
    if (status & (1 << (*first - 'A'))) {
    break;
    }
    }
    if (*first != '\0') {
    continue;
    }
    // 没有冲突,选择它
    for (first = item; *first != '\0'; first++) {
    status |= 1 << (*first - 'A');
    }
    selected[step] = index;
    // 检测是否包含所有项
    if ((status & 0x3f) == 0x3f) {
    for (int i = 0; i <= step; i++) {
    cout << data[selected[i]] << ", ";
    }
    cout << endl;
    } else {
    // 没有包含所有项,继续从下一个开始尝试
    find(index + 1, selected, step + 1, status);
    }
    // 回退,取消本次选择
    for (first = item; *first != '\0'; first++) {
    status &= ~(1 << (*first - 'A'));
    }
    }
    }

    int main(int argc, char const *argv[])
    {
    int selected[6] = {0};
    find(0, selected, 0, 0);
    return 0;
    }

    输出:

    AB, C, EF, D,
    AB, EF, CD,
    ACF, BE, D,

    其中, status 的低 6 位表示当前哪些项已经出现。
    liberize
        5
    liberize  
       2015-12-09 12:44:14 +08:00
    可以把每一个集合转成一个整数,比如 (A, C, F) 转成 0b00100101 ,然后全部用位运算来判断,代码可以更简洁,效率也更高
    liberize
        6
    liberize  
       2015-12-09 13:22:03 +08:00
    把每一个集合转成一个整数可以构造一张哈希表,然后当 status 中只剩下两三项没有填满时,比如只剩下 AB ,求 (A, B) 的所有分割,即 (A), (B) 和 (A, B),然后直接从哈希表中检测这些子集是否存在
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2539 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 01:27 · PVG 09:27 · LAX 17:27 · JFK 20:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.