文字列のリスト内の同じ位置にある文字を見つけるアルゴリズムですか？

Question

私が持っていると仮定します。

1. トビー
2. タイニー
3. トーリー
4. Tily

簡単にすべての同じ位置に共通の文字のリストを作成することができるアルゴリズムがありますこれらの文字列？ （この場合、共通の文字は位置0に 'T'、位置3に 'y'）

DNA配列一致に使用されるアルゴリズムのいくつかを見てみましたが、それらの位置に関係なく共通の部分文字列

Answer 1

特定の位置にあるすべての文字列に共通する文字のリストを見つけることは、やや単純です。一度に各文字位置の1文字の位置ごとに各文字列を繰り返してください。いずれかの文字列がそれに最も近い隣の文字列の文字と一致しない場合、その位置には共通文字が含まれません。

i = 0〜長さ-1 ... Si [x]！= Si + 1 [x]を見つけると、次の位置x + 1にスキップできます。

ここで、Siはリスト内のi番目の文字列です。そして[x]は位置xの文字です。

Answer 2

かなり貧弱なパフォーマンスは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 3

に私は特に最適化されたものを考えることはできません。

あなたはあまりにも難しいことではありませんこれは、このような何かを行うことができます。

 //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 4

このようなことはどうですか？実行の終わりに

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 
    } 
} 

、結果は以下のようになります。commonletters.rbでこれを入れて

#!/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] } 

：

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

Answer 5

ここでルビーの5行におけるアルゴリズムです。使用例：

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

そのINPUT.TXTと仮定するとは含まれています

Toby 
Tiny 
Tory 
Tily 

これはあなたがそれで投げる何でも入力で動作するはずです。入力ファイルが空の場合は破損しますが、おそらくそれを修正することができます。これはO（n）です（nは入力の合計文字数です）。

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)] 

出力します：

Answer 6

そして、ここでは、Pythonでの些細なバージョンです

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

編集：ここではタプルの（潜在的に）巨大なリストを作成する必要はありません、より良いバージョンがあります： Lispでは

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 7

：

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) 

あなたがposiitons気遣い、ちょうど一般的な文字のリストを必要としない場合：

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

私はこれがアルゴリズムではなかったことを認めます...これを使用して既存の機能

手動で実行する場合は、前述のように、指定されたインデックスのすべての文字を互いに比較するループを行います。それらがすべて一致する場合は、一致する文字を保存します。

Answer 8

#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; 
}