☰

理論

tag-icon • tag-icon text-processing awk algorithms
理論

2つの列を持つスペースまたはカンマ区切りのテーブルがあり、各行は2つの単語の同等性を表します。

A B  
B C  
B D  
C E  
F G

私が望むのは、互いに等しいすべての単語をリストする各行を持つテーブルです。

A B C D E  
F G

つまり、両方の単語が同じ入力行に表示される場合は、最終的に同じ出力行に表示される必要があります。

どんなツールでも可能です。

答え1

Pythonは入力ファイルを引数で始めます。 

import sys

res = []  # list of lists
for line in open(sys.argv[1]):
    try:
        x, y = line.split()  # split on space
    except ValueError:
        line = line.rstrip()
        x, y = line.split(',')  # retry with comma
    for l in res:
        if x in l:
            if y not in l:
                l.append(y)
            break
    else:
        res.append([x, y])

for line in res:
    print ' '.join(line)

テストでは、if y not in l:同じ値を2回追加することをスキップします。これが必要かどうか、ソースにそのような例外があるかどうかはわかりません。テストを省略して常に実行できますl.append(y)。

コードは最初にスペースに分割し、次にコンマを再試行します。これは、カンマで区切られた行にスペースがないと仮定します（つまりスペースではないA, B）。

ネストされたforループは（私が知る限り）Pythonの機能を使用します。つまり、breakステートメントではなく、elseループがExhaustionを介して終了したときにのみ実行されます。forつまりx、見つからない場合は、そのペアが新しいリストとして追加されますres。

答え2

理論

この問題はコレクションを分ける入力する同等クラス、入力ファイルにはペアごとの同等性がリストされます。この問題は、次のツールを使用して解決できます。お互いのセットデータ構造

あまり抽象的でない例は、例えば、同義語のペアが与えられた同義語のグループに単語を分割することである。

large big
big great
great vast
small little
little tiny

になる:

large big great vast
small little tiny

ルビー溶液

互いのセットはRuby標準ライブラリでは使用できないため、Rubyを使用してこれをエミュレートしましたHash（他の場所では「連想配列」、「辞書」、「マップ」とも呼ばれます）。

#!/usr/bin/env ruby
# new elements end up in "singleton subsets"
subsets = Hash.new { |subsets, element| subsets[element] = [element] }
ARGF.each do |line|
  x, y = line.scan(/[^\s,]/)
  # these two emulate disjoint-set's "find" operation
  x_set = subsets[x]
  y_set = subsets[y]
  # and this loop implements disjoint-set's "union"
  y_set.each do |element, _|
    subsets[element] = x_set << element
  end unless x_set == y_set
end
puts subsets.values.uniq.map{|set| set.join(" ")}

使用法

これには、コマンドラインにファイル名が必要であるか、標準入力にデータが必要です。

$ ruby so-162730.rb input.txt
A B C D E
F G

$ ruby so-162730.rb < input.txt
A B C D E
F G

奇妙なソリューション

たぶんこのサイトに適しているかもしれません。

ここでは、互いのセットのわずかに異なる実装を使用します。各サブセットは、対応する要素の1つ（「リーダー」）として表示されます。これは結合操作を遅くしますが、awkの単純なデータ型を使用して実装する方が簡単です。

{
  union(find($1), find($2));
}

END {
  format_subsets();
  for(i in subsets)
    print subsets[i];
}

function find(element) {
  if (!leaders[element])
    leaders[element] = element;
  return leaders[element];
}

function union(leader_1, leader_2) {
  for(i in leaders)
    if (leaders[i] == leader_2)
      leaders[i] = leader_1;
}

function format_subsets() {
  for(element in leaders) {
    leader = leaders[element]
    subsets[leader] = (subset = subsets[leader]) ? (subset OFS element) : element;
  }
}

使用法

$ awk -f so-162730.awk < input.txt
A B C D E
F G

またはスペースまたはカンマで区切られた入力の場合：

$ awk -f so-162730.awk -F '[[:space:]]+|,' input.txt
A B C D E
F G

関連情報