7

イベントのリストのセットがあります。イベントは常に特定の順序で発生しますが、すべてのイベントが常に発生するとは限りません。入力例を次に示します。

[[ do, re, fa, ti ],
 [ do, re, mi ],
 [ do, la, ti, za ],
 [ mi, fa ],
 [ re, so, za ]]

入力値には固有の順序はありません。それらは実際には「シンボリックリンクの作成」や「検索の再インデックス」などのメッセージです。それらは個々のリストでソートされますが、最初のリストの「fa」と 2 番目のリストの「mi」だけを見て、どちらが先に来るかを判断する方法はありません。

その入力を取得して、すべてのイベントの並べ替えられたリストを生成できるようにしたいと思います。

[ do, re, mi, fa, so, la, ti, za ]

さらに良いことに、カウントなどの各イベントに関する情報:

[ [do, 3], [re, 3], [mi, 2],
  [fa, 2], [so, 1], [la, 1],
  [ti, 1], [za, 2] ]

私がしていることに名前はありますか？受け入れられているアルゴリズムはありますか? 私はこれを Perl で書いていますが、それが問題なら、疑似コードでも構いません。

私の入力例を考えると、おそらく「正しい」順序を保証できないことはわかっています。しかし、私の実際の入力にはさらに多くのデータポイントがあり、ある程度の賢さで 95% 正しいと確信しています (これだけで十分です)。必要がなければ、車輪を再発明したくありません。

4

10 に答える 10

3

を使用して、観察した順序からtsort妥当な (必ずしも一意であるとは限りませんが) 並べ替え順序 (トポロジー順序と呼ばれる) を推測できます。あなたの問題に構造が似ているtsortの元の使用法を読むことに興味があるかもしれません。

tsort非循環グラフが必要であることに注意してください。あなたの例では、これは、あるシーケンスで do の後に re が続き、別のシーケンスで re の後に do が表示されないことを意味します。

#! /usr/bin/perl

use warnings;
use strict;

use IPC::Open2;

sub tsort {
  my($events) = @_;

  my $pid = open2 my $out, my $in, "tsort";

  foreach my $group (@$events) {
    foreach my $i (0 .. $#$group - 1) {
      print $in map "@$group[$i,$_]\n", $i+1 .. $#$group;
    }
  }

  close $in or warn "$0: close: $!";

  chomp(my @order = <$out>);
  my %order = map +(shift @order => $_), 0 .. $#order;
  wantarray ? %order : \%order;
}

データがまばらであると説明したため、上記のコードはtsort、イベントの隣接行列に関する可能な限り多くの情報を提供します。

その情報があれば、ヒストグラムを計算し、そのコンポーネントを並べ替えるのは簡単です。

my $events = [ ... ];

my %order = tsort $events;

my %seen;
do { ++$seen{$_} for @$_ } for @$events;

my @counts;
foreach my $event (sort { $order{$a} <=> $order{$b} } keys %seen) {
  push @counts => [ $event, $seen{$event} ];
  print "[ $counts[-1][0], $counts[-1][1] ]\n";
}

あなたが提供した質問の入力について、出力は

[ し、3 ]
[ラ、1]
[ re, 3 ]
[そう、1]
[ mi, 2 ]
[ fa, 2 ]
[ ti, 2 ]
[座、2]

ソルフェージュの順序を知っているので、これはおかしいように見えますが、re と la はによって定義される半順序$eventsでは比較できません。

于 2010-07-09T20:22:41.247 に答える
3

理論的に言えば、次のアルゴリズムを提案させてください。

  1. 有向グラフを作成します。
  2. 各入力 [ X, Y, Z ] に対して、エッジ X->Y および Y->Z がまだ存在しない場合は作成します。
  3. グラフのトポロジカル ソートを実行します。
  4. 出来上がり！

PS
これは、すべてのイベントが特定の順序で (常に!) 発生することを前提としています。そうでない場合、問題は NP-Complete になります。

PPS
そして、あなたが何か役に立つものを持っているように：Sort::Topological（実際に機能するかどうかはわかりませんが、正しいようです）

于 2010-07-09T18:48:16.433 に答える
2

多くのコードを書くことに興味がない場合は、unixコマンドラインユーティリティを使用できますtsort。

$ tsort -
do re
re fa
fa ti
do re
re mi
do la
la ti
ti za
mi fa
re so
so za

これは、サンプル入力のすべてのペアのリストです。これは出力として生成されます：

do
la
re
so
mi
fa
ti
za

これは基本的にあなたが望むものです。

于 2010-07-09T20:06:07.310 に答える
0

これが何と呼ばれるかはよくわかりませんが、配列の配列を入力として指定して順序を見つける方法を見つけました。基本的に、擬似コードは次のとおりです。

10すべての配列で最も古いアイテムを検索します
20それをリストにプッシュします
30すべての配列からそのアイテムを削除します
40アイテムが残っている場合は10に進みます

動作するプロトタイプは次のとおりです。

#!/usr/bin/perl

use strict;

sub InList {
    my ($x, @list) = @_;
    for (@list) {
        return 1 if $x eq $_;
    }
    return 0;
}

sub Earliest {
    my @lists = @_;
    my $earliest;
    for (@lists) {
        if (@$_) {
            if (!$earliest
                || ($_->[0] ne $earliest && InList($earliest, @$_))) {

                $earliest = $_->[0];
            }
        }
    }
    return $earliest;
}

sub Remove {
    my ($x, @lists) = @_;

    for (@lists) {
        my $n = 0;
        while ($n < @$_) {
            if ($_->[$n] eq $x) {
                splice(@$_,$n,1);
            }
            else {
                $n++
            }
        }
    }
}

my $list = [
    [ 'do', 're', 'fa', 'ti' ],
    [ 'do', 're', 'mi' ],
    [ 'do', 'la', 'ti', 'za' ],
    [ 'mi', 'fa' ],
    [ 're', 'so', 'za' ]
];

my @items;

while (my $earliest = Earliest(@$list)) {
    push @items, $earliest;
    Remove($earliest, @$list);
}

print join(',', @items);

出力：

do、re、mi、fa、la、ti、so、za

于 2010-07-09T20:42:41.247 に答える
0

解決：

これにより、質問者によって変更される前の元の質問が解決されます。

#!/usr/local/bin/perl -w
use strict; 

   main();
    
   sub main{
      # Changed your 3-dimensional array to a 2-dimensional array
      my @old = (
                   [ 'do', 're', 'fa', 'ti' ],
                   [ 'do', 're', 'mi' ],
                   [ 'do', 'la', 'ti', 'za' ],
                   [ 'mi', 'fa' ],
                   [ 're', 'so', 'za' ]
                );
      my %new;

      foreach my $row (0.. $#old ){                           # loop through each record (row)
         foreach my $col (0..$#{$old[$row]} ){                # loop through each element (col)                    
            $new{ ${$old[$row]}[$col] }{count}++;
            push @{ $new{${$old[$row]}[$col]}{position} } , [$row,$col];
         }
      }

      foreach my $key (sort keys %new){
         print "$key : $new{$key} " , "\n";                   # notice each value is a hash that we use for properties 
      }      
   }

情報を取得する方法：

   local $" = ', ';                       # pretty print ($") of array in quotes
   print $new{za}{count} , "\n";          # 2    - how many there were
   print "@{$new{za}{position}[1]} \n";   # 4,2  - position of the second occurrence
                                          #        remember it starts at 0

基本的に、ハッシュ内の要素の一意のリストを作成します。countこれらの要素ごとに、スカラーとの配列を含む「プロパティ」ハッシュがありpositionます。配列内の要素の数は、元の要素の出現回数に基づいて変化する必要があります。

配列のスカラーを常にposition取得して同じ数を取得できるため、スカラープロパティは実際には必要ありません。count注：配列から要素を追加/削除したpositionことがあり、それらの意味が相関しない場合。

  • 例：print scalar @{$new{za}{position}};あなたに同じものを与えるでしょうprint $new{za}{count};
于 2010-07-09T21:20:31.437 に答える
0 
perl -de 0
  DB<1> @a = ( ['a','b','c'], ['c','f'], ['h'] ) 
  DB<2> map { @m{@{$_}} = @$_ } @a
  DB<3> p keys %m
chabf

私が考えることができる最も速いショートカット。いずれにせよ、少なくとも一度は繰り返し処理する必要があります...

于 2010-07-09T18:42:06.793 に答える
0

これはMerge Sortの最適な候補です。アルゴリズムのかなり良い表現については、ここのウィキペディアのページにアクセスしてくださいhttp://en.wikipedia.org/wiki/Merge_sort

あなたが説明したことは、実際にはマージソートのサブセット/小さな調整です。ソートされていない配列から始めるのではなく、一緒にマージしたいソートされた配列のセットがあります。ウィキペディアのページで説明されているように、配列のペアとマージ関数の結果で説明されているように、単一の配列（ソートされる）になるまで「マージ」関数を呼び出すだけです。

出力を希望どおりに微調整するには、あるイベントが別のイベントより小さい、等しい、または大きい場合に返される比較関数を定義する必要があります。次に、マージ関数が等しい 2 つのイベントを見つけたら、それらを 1 つのイベントにまとめて、そのイベントのカウントを保持できます。

于 2010-07-09T18:45:26.173 に答える
0

あなたの質問は、事前に決められた順序ではないと言っていましたので、これは関係ないかもしれません.

パールコード:

$list = [
    ['do', 're', 'fa', 'ti' ],
    ['do', 're', 'mi' ],
    ['do', 'la', 'ti', 'za' ],
    ['mi', 'fa' ],
    ['re', 'so', 'za' ]
];
%sid = map{($_,$n++)}qw/do re mi fa so la ti za/;

map{map{$k{$_}++}@$_}@$list;
push @$result,[$_,$k{$_}] for sort{$sid{$a}<=>$sid{$b}}keys%k;

print "[@$_]\n" for(@$result);

出力：

[do 3]
[re 3]
[mi 2]
[fa 2]
[so 1]
[la 1]
[ti 2]
[za 2]
于 2010-07-10T15:32:53.640 に答える
0

大まかに言うと、私が付けたい名前は「ハッシュ」です。名前と値のペアに物事を入れています。ある程度の順序を維持したい場合は、順序を維持する配列でハッシュを補足する必要があります。その順番が私にとっての「出会いの順番」です。

use strict;
use warnings;

my $all 
    = [[ 'do', 're', 'fa', 'ti' ],
       [ 'do', 're', 'mi' ],
       [ 'do', 'la', 'ti', 'za' ],
       [ 'mi', 'fa' ],
       [ 're', 'so', 'za' ]
     ];

my ( @order, %counts );

foreach my $list ( @$all ) { 
    foreach my $item ( @$list ) { 
        my $ref = \$counts{$item}; # autovivs to an *assignable* scalar.
        push @order, $item unless $$ref;
        $$ref++;
    }
}

foreach my $key ( @order ) { 
    print "$key: $counts{$key}\n";
}

# do: 3
# re: 3
# fa: 2
# ti: 2
# mi: 2
# la: 1
# za: 2
# so: 1

このような答えは他にもありますが、私のものにはこのきちんとした自動有効化のトリックが含まれています。

于 2010-07-09T19:31:15.450 に答える