Intereting Posts
Защищенные паролем zip-архивы открываются без пароля Что означает Chromium NET :: ERR_CERT_COMMON_NAME_INVALID? Служба Bumblebee (Optimus) не начнет работать с 3.4 ядра на Fedora 16 Использование переменной * в сценарии оболочки для ссылки на все файлы в папке Как создать интерактивный скрипт bash для сбора аргументов для команды в Linux? Перечислить временные файлы по числовому значению, имеющему число больше заданного постоянно изменяющегося имени файла Bash: `test` находит файл, но` source` wont Почему я не могу использовать renice для повышения «хорошего значения» процесса? Есть ли способ остановить случайные пакеты программного обеспечения от удаленной передачи ваших файлов? как посмотреть значение данных по индексу поиска? Как отправить приложения командной строки прямо на задний план? renice не работает в macOS Sierra Заменить кучу файлов, поддерживающих путь iptables перенаправляет внешние запросы на 127.0.0.1 Почему и как отслеживать / var / log / dmesg с контролем версий

Как я могу разбить набор слов на пары, которые должны совпадать?

У меня есть таблица с пробелом или запятой с двумя столбцами, каждая строка соответствует эквивалентности двух слов.

ABBCBDCEFG 

То, что я хочу, это таблица с каждой строкой, в которой перечислены все взаимно эквивалентные слова.

 ABCDEFG 

То есть, если два слова когда-либо встречаются в одной строке ввода, они должны быть в той же строке вывода.

Любой инструмент будет делать.

В 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: пропускает добавление одного и того же значения дважды, я не уверен, что это требуется, или если у источника есть такие аномалии. Вы можете оставить тест и всегда выполнять l.append(y) .

Код сначала пытается разбить по пространству, а затем повторяет запятую. Это предполагает, что разделенные запятой строки не имеют места в них (т. Е. Не являются A, B ).

Вложенный цикл for использует (AFAIK) особенность python: else выполняется только в том случае, если цикл for заканчивается исчерпанием, а не через оператор break. Это означает, что если x не найден, пара добавляется как новый список в res .

теория

Эта проблема известна как разбиение набора на классы эквивалентности , с входным файлом, содержащим парные эквивалентности. Его можно решить с помощью структуры данных с несвязанными наборами .

Менее абстрактным примером является, например, разбиение слов на группы синонимов с учетом пары синонимов:

 large big big great great vast small little little tiny 

будет выглядеть так:

 large big great vast small little tiny 

рубиновый раствор

Disjoint set недоступен в стандартной библиотеке 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(" ")} 

Применение

это ожидает имена файлов в командной строке или данные по stdin:

 $ ruby so-162730.rb input.txt ABCDE FG $ ruby so-162730.rb < input.txt ABCDE FG 

Решение awk

Возможно, более подходящий для этого сайта.

Здесь я использую несколько другую реализацию disjoint-set: каждое подмножество представлено одним из его элементов («leader»). Это делает работу соединения медленнее, но проще реализовать с помощью простых типов данных 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 ABCDE FG 

Или для ввода с пробелами или запятыми:

 $ awk -f so-162730.awk -F '[[:space:]]+|,' input.txt ABCDE FG