linux - 需要更好的数字组合解决方案

Question

我有包含以下条目的文件:

1,2
2,3
4,5
1,3
1,4
5,6
...

这告诉 ids:第一列与第二列匹配。现在我想找到所有只有所有组合的 id 组。即需要输出以下内容:

1,2,3
4,5
1,4
5,6

我尝试为解决方案编写一个 perl 脚本:

while(<STDIN>) {
    if(m/^(\d+),(\d+)/) {
        $dub{$1}{$2} = 1;
        $dub{$2}{$1} = 1;
        $hs{$1} = 1;
        $hs{$2} = 1;
    }
}

$i=0;
foreach $a (keys %dub) {
    $grp[$i]{$a} = 1;
    foreach $b (keys %{$dub{$a}}) {
        $grp[$i]{$b} = 1;
        foreach $c (keys %hs) {
            if($c == $a || $c == $b) { next; }
            $flag = 1;
            foreach $d (keys %{$grp[$i]}) {
                if(!$dub{$d}{$c}) {
                    $flag = 0;
                    last;
                }
            }
            $grp[$i]{$c} = 1 if($flag);
        }
        $i++;
    }
}

for($i=0; $i<=$#grp; $i++) {
    print join(",", (keys %{$grp[$i]}))."\n";
}

但这需要大量的执行时间。以上脚本是否有更好的解决方案、算法或性能调整？LAMP 中的任何解决方案都值得赞赏。谢谢

编辑:

这样想:(1,2) 被定义为“1 和 2 相似”(2,3) 被定义为“2 和 3 相似”(1,4) 被定义为“1 和 4 相似”(1,3) 定义为“1 和 3 相似”

根据这些相似性，我得出结论，组 (1,2,3) 彼此相似，但组 (1,2,3,4) 不相似。为了形成组 (1,2,3,4)，数据中应该有其他条目，如 (2,4) 和 (3,4)。

最后我想找到给定坐标集中的所有组。

Answer 1

根据我的理解，{1,2,3} 属于同一组，因为它们都指向彼此({1,2}、{2,3}、{1,3} 存在)。因此，我们可以将这个问题简化为在无向图中寻找派系，这是 NP-Complete 问题。因此，每种解决方案在处理大数据时都非常低效。