有 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)...以此类推,再求他们的交集???复杂度是多少?这个解法看起来不像最优解。有别的招吗?
1
statm 2015-12-09 04:23:01 +08:00
LZ 可以去搜搜 BFS 算法
|
2
ruandao 2015-12-09 07:36:07 +08:00
是求全排列吗?
|
3
messyidea 2015-12-09 08:26:49 +08:00 via Android
是不是只有 A 到 F 6 项,里面元素可以重复吗。比如
(a , b)和(a , c),可以先找出所有项,每一项用状态压缩把他们压成一个数字,然后搜索起来方便一点,只需要&操作,然后看结果是否等于(11111)[二进制]就可以了 |
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 位表示当前哪些项已经出现。 |
5
liberize 2015-12-09 12:44:14 +08:00
可以把每一个集合转成一个整数,比如 (A, C, F) 转成 0b00100101 ,然后全部用位运算来判断,代码可以更简洁,效率也更高
|
6
liberize 2015-12-09 13:22:03 +08:00
把每一个集合转成一个整数可以构造一张哈希表,然后当 status 中只剩下两三项没有填满时,比如只剩下 AB ,求 (A, B) 的所有分割,即 (A), (B) 和 (A, B),然后直接从哈希表中检测这些子集是否存在
|