私が持っているとします：
- トビー
- 小さい
- トリー
- タイリー
これらすべての文字列の同じ位置にある一般的な文字のリストを簡単に作成できるアルゴリズムはありますか? (この場合、一般的な文字は位置 0 の 'T' と位置 3 の 'y' です)
DNA シーケンス マッチングに使用されるアルゴリズムのいくつかを調べてみましたが、それらのほとんどは、位置に関係なく共通の部分文字列を見つけるために使用されているようです。
8 に答える
3
特定の位置にあるすべての文字列に共通する文字のリストを見つけるのは簡単です。一度に1文字の位置ごとに、各文字列を繰り返し処理します。いずれかの文字列の文字が最も近い隣接文字列の文字と一致しない場合、その位置には共通の文字が含まれていません。
任意のi=0から長さ-1の場合...Si[x]！= Si + 1 [x]が見つかったら、次の位置x+1にスキップできます。
ここで、Siはリストのi番目の文字列です。そして、[x]は位置xの文字です。
于 2008-09-16T01:54:57.157 に答える
1
特に最適化されたものは考えられません。
あなたはこのようなことをすることができますが、それほど難しいことではありません：
//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++;
}
}
これにより、リスト内のすべてで同じ文字の配列が得られます。
于 2008-09-16T02:07:01.150 に答える
1
このようなものはどうですか？
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}
}
于 2008-09-16T02:12:24.617 に答える
1
パフォーマンスがかなり低い一般的なコード 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);
于 2008-09-16T02:03:49.850 に答える
1
#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;
}
于 2008-09-21T18:50:03.107 に答える
1
ルビーの5行のアルゴリズムは次のとおりです。
#!/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 は入力内の文字の総数) です。
于 2008-09-16T02:24:45.213 に答える
1
そして、ここに 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')]
編集:タプルの(潜在的に)巨大なリストを作成する必要のないより良いバージョンがあります:
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)]
于 2008-09-19T17:16:16.563 に答える
0
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でそれを行う方法にすぎません
前述のように、手動で実行したい場合は、特定のインデックスにあるすべての文字を互いに比較してループします。それらがすべて一致する場合は、一致する文字を保存します。
于 2008-09-19T18:35:16.343 に答える