1

次のエントリを含むファイルがあります。

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

これは ID を示します。最初の列は 2 番目の列と一致します。ここで、すべての組み合わせのみを持つすべての 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

私の理解では、すべてが互いに指しているため、{1,2,3}は同じグループに属します（{1,2}、{2,3}、{1,3}が存在します）。したがって、この問題を無向グラフでクリークを見つけることに減らすことができます。これはNP完全問題です。したがって、すべてのソリューションはビッグデータでは非常に非効率的です。

于 2013-03-21T21:15:28.433 に答える
0

あなたは、私たちが使用するはずのアルゴリズムを実際に説明していません。入力が「1,2,3,4」ではなく「1,2,3」と「1,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

これは私のために働く：

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 に答える