解一道算法题

V2EX = way to explore

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

现在注册

已注册用户请登录

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

有 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)...以此类推，再求他们的交集？？？复杂度是多少？这个解法看起来不像最优解。有别的招吗？

包含

a-f

解法

以此类推

6 条回复 2015-12-09 13:22:03 +08:00

statm

2015-12-09 04:23:01 +08:00

LZ 可以去搜搜 BFS 算法

ruandao

2015-12-09 07:36:07 +08:00

是求全排列吗?

messyidea

2015-12-09 08:26:49 +08:00 via Android

是不是只有 A 到 F 6 项，里面元素可以重复吗。比如
(a ， b)和(a ， c)，可以先找出所有项，每一项用状态压缩把他们压成一个数字，然后搜索起来方便一点，只需要&操作，然后看结果是否等于(11111)[二进制]就可以了

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

2015-12-09 12:44:14 +08:00

可以把每一个集合转成一个整数，比如 (A, C, F) 转成 0b00100101 ，然后全部用位运算来判断，代码可以更简洁，效率也更高

liberize

2015-12-09 13:22:03 +08:00

把每一个集合转成一个整数可以构造一张哈希表，然后当 status 中只剩下两三项没有填满时，比如只剩下 AB ，求 (A, B) 的所有分割，即 (A), (B) 和 (A, B)，然后直接从哈希表中检测这些子集是否存在