Алгоритм нахождения символов в тех же позициях в списке строк?

Question

Предположим, у меня есть:

1. Toby
2. Крошка
3. Тори
4. Tily

Существует ли алгоритм, который может легко создать список общих символов в одинаковых позициях во всех этих строках? (в этом случае обычными символами являются 'T' в позиции 0 и 'y' в позиции 3)

Я попытался взглянуть на некоторые алгоритмы, используемые для сопоставления последовательностей ДНК, но кажется, что большинство из них просто используются для поиска общих подстрок независимо от их положения.

Answer 1

Найти список символов, которые являются общими для ВСЕХ строк в определенной позиции, тривиально просто. Просто итерируйте по каждой строке для каждой позиции символа 1 позиция символа за раз. Если какой-либо символ строки не совпадает с символом строки ближайшего соседа, то позиция не содержит общего символа.

Для любого i = 0 до длины -1 ... Как только вы найдете Si [x]! = Si + 1 [x], вы можете перейти к следующей позиции x + 1.

Где Si - это i-я строка в списке. И [x] - это символ в позиции x.

Answer 2

#include <iostream>

int main(void)
{
    char words[4][5] = 
    {
        "Toby",
        "Tiny",
        "Tory",
        "Tily"
    };

    int wordsCount = 4;
    int lettersPerWord = 4;

    int z;
    for (z = 1; z < wordsCount; z++)
    {
        int y;
        for (y = 0; y < lettersPerWord; y++)
        {
            if (words[0][y] != words[z][y])
            {
                words[0][y] = ' ';
            }
        }
    }

    std::cout << words[0] << std::endl;

    return 0;
}

Answer 3

А вот тривиальная версия на Python:

items = ['Toby', 'Tiny', 'Tory', 'Tily']
tuples = sorted(x for item in items for x in enumerate(item))
print [x[0] for x in itertools.groupby(tuples) if len(list(x[1])) == len(items)]

Какие отпечатки:

[(0, 'T'), (3, 'y')]

Edit: вот лучшая версия, которая не требует создания (потенциально) огромного списка кортежей:

items = ['Toby', 'Tiny', 'Tory', 'Tily']
minlen = min(len(x) for x in items)
print [(i, items[0][i]) for i in range(minlen) if all(x[i] == items[0][i] for x in items)]

Answer 4

Вот алгоритм в 5 строках ruby:

#!/usr/bin/env ruby
chars = STDIN.gets.chomp.split("")
STDIN.each do |string|
  chars = string.chomp.split("").zip(chars).map {|x,y| x == y ? x : nil }
end
chars.each_index {|i| puts "#{chars[i]}  #{i}" if chars[i] }

Поместите это в commonletters.rb. Пример использования:

$ commonletters.rb < input.txt
T  0
y  3

Предполагая, что input.txt содержит:

Toby
Tiny
Tory
Tily

Это должно работать с любыми входными данными, которые вы к нему добавляете. Он сломается, если входной файл пуст, но вы, вероятно, можете это исправить самостоятельно. Это O (n) (n - общее количество символов на входе).

Answer 5

Как насчет этого?

strings = %w(Tony Tiny Tory Tily)
positions = Hash.new { |h,k| h[k] = Hash.new { |h,k| h[k] = 0 } }
strings.each { |str| 
  0.upto(str.length-1) { |i| 
    positions[i][str[i,1]]+=1 
  }
}

В конце выполнения результат будет:

positions = {
  0=>{"T"=>4},
  1=>{"o"=>2, "i"=>2}, 
  2=>{"l"=>1, "n"=>2, "r"=>1},
  3=>{"y"=>4}
}

Answer 6

Я не могу придумать ничего особенно оптимизированного.

Вы можете сделать что-то вроде этого, что не должно быть слишком сложно:

        //c# -- assuming your strings are in a List<string> named Names
        int shortestLength = Names[0].Length, j;
        char[] CommonCharacters;
        char single;

        for (int i = 1; i < Names.Count; i++)
        {
            if (Names[i].Length < shortestLength) shortestLength = Names[i].Length;
        }

        CommonCharacters = new char[shortestLength];
        for (int i = 0; i < shortestLength; i++)
        {
            j = 1;
            single = Names[0][i];
            CommonCharacters[i] = single;
            while (j < shortestLength)
            {
                if (single != Names[j][i])
                {
                    CommonCharacters[i] = " "[0];
                    break;
                }
                j++;
            }
        }

Это даст вам массив одинаковых символов для всего списка.

Answer 7

Какой-то общий код с довольно низкой производительностью O (n ^ 2)

str[] = { "Toby", "Tiny", "Tory", "Tily" };
result = null;
largestString = str.getLargestString(); // Made up function
str.remove(largestString)
for (i = 0; i < largestString.length; i++) {
   hits = 0;
   foreach (str as value) {
      if (i < value.length) {
         if (value.charAt(i) == largestString.charAt(i))
            hits++;
      }
   }
   if (hits == str.length)
      result += largestString.charAt(i);
}
print(str.items);

Answer 8

In lisp:

CL-USER> (defun common-chars (&rest strings)
           (apply #'map 'list #'char= strings))
COMMON-CHARS

Просто передайте строки:

CL-USER> (common-chars "Toby" "Tiny" "Tory" "Tily")
(T NIL NIL T)

Если вы хотите самих персонажей:

CL-USER> (defun common-chars2 (&rest strings)
           (apply #'map
                  'list
                  #'(lambda (&rest chars)
                      (when (apply #'char= chars)
                        (first chars))) ; return the char instead of T
                  strings))
COMMON-CHARS2

CL-USER> (common-chars2 "Toby" "Tiny" "Tory" "Tily")
(#\T NIL NIL #\y)

Если вы не заботитесь о позициях и хотите просто список общих символов:

CL-USER> (format t "~{~@[~A ~]~}" (common-chars2 "Toby" "Tiny" "Tory" "Tily"))
T y 
NIL

Я признаю, что это был не алгоритм ... просто способ сделать это в lisp, используя существующую функциональность

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