1

我有以下条目的文件：

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)。

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

4

3 回答 3

0

这对我有用：

use Data::Dump;

my @results;
my ($last_a, $last_b) = (0,0);

while(<DATA>) {
    chomp;
    my ($a, $b) = split /,/;
    if( $last_b == $a ) {
        my $last_item = $results[$#results];
        push @$last_item, $b;
    }
    else {
        push @results, [$a, $b];
    }
    ($last_a,  $last_b) = ($a, $b);
}

dd @results; # ([1, 2, 3], [4, 5], [1, 3], [1, 4], [5, 6])

__DATA__
1,2
2,3
4,5
1,3
1,4
5,6
于 2013-03-21T14:00:05.883 回答
0

您还没有真正描述我们应该使用的算法。我真的不明白为什么您的输入会生成“1,2,3”和“1,4”，而不仅仅是“1,2,3,4”。

但这就是你想要的吗？

#!/usr/bin/perl

use strict;
use warnings;
use 5.010;

my %data;
while (<DATA>) {
  chomp;
  my ($k, $v) = split /,/;
  push @{ $data{$k} }, $v;
}

foreach (sort keys %data) {
  say "$_,", join ',', @{ $data{$_ } };
}

__DATA__
1,2
2,3
4,5
1,3
1,4
5,6
于 2013-03-21T14:46:24.330 回答
0

据我了解，{1,2,3} 属于同一组，因为它们都指向对方（{1,2}、{2,3}、{1,3} 存在）。因此，我们可以将这个问题简化为在无向图中寻找团，即 NP-Complete 问题。因此，每个解决方案在大数据上的效率都非常低。

于 2013-03-21T21:15:28.433 回答