I have a space or comma separated table with two columns, each row representing equivalence of the two words.
A B B C B D C E F G What I want is a table with each row listing all mutually equivalent words.
A B C D E F G That is if two words ever occur on the same row of input they must end up in the same row of the output.
Any tool would do.
In python, start with the input file as an argument:
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) The test if y not in l: skips adding the same value twice, I am not sure if that is wanted, or if the source has such anomalies. You can leave out the test and always execute l.append(y).
The code tries to split on space first, then retries comma. This assumes comma separated lines have no space in them (i.e. are not A, B).
The nested for loop uses (AFAIK) a python particularity: the else is only executed if the for loop ends through exhaustion, that is not through the break statement. This means if x is not found, the pair is appended as new list to res.
This problem is known as partitioning a set into equivalence classes, with input file listing pairwise equivalences. It can be solved with the help of a disjoint-set data structure.
Less abstract example is e.g. partitioning words into groups of synonyms given pairs of synonyms:
large big big great great vast small little little tiny becomes:
large big great vast small little tiny Disjoint set isn't available in ruby standard library, so I emulate it using a ruby Hash (known elsewhere as "associative array", "dictionary", "map").
#!/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(" ")} this expects filenames on the command line or data on stdin:
$ 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 Perhaps more appropriate for this site.
Here I use a slightly different implementation of disjoint-set: each subset is represented by one of its elements ("leader"). This makes union operation slower, but is easier to implement with awk's simple data types.
{ 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 Or for whitespace or comma separated input:
$ awk -f so-162730.awk -F '[[:space:]]+|,' input.txt A B C D E F G
A B D C Ealso correct for the first line?DandEwill only be in the first row after having been added by processing the previous rows. What if you haveE Gfurther down? How should that be dealt with? Also, which is it, space or comma?