Algorithme pour trouver des caractères aux mêmes positions dans une liste de chaînes?

Question

Supposons que j'ai:

1. Toby
2. Minuscule
3. Tory
4. Tily

Existe-t-il un algorithme permettant de créer facilement une liste de caractères communs aux mêmes positions dans toutes ces chaînes? (dans ce cas, les caractères communs sont "T" en position 0 et "y" en position 3)

J'ai essayé d'examiner certains des algorithmes utilisés pour l'appariement des séquences d'ADN, mais il semble que la plupart d'entre eux ne servent qu'à trouver des sous-chaînes communes, quelle que soit leur position.

Answer 1

La recherche d'une liste de caractères communs dans TOUTES les chaînes à une certaine position est trivialement simple. Il suffit d’itérer sur chaque chaîne pour chaque position de caractère une position de caractère à la fois. Si le caractère d'une chaîne ne correspond pas à celui de la chaîne voisine la plus proche, la position ne contient pas de caractère commun.

Pour tout i = 0 à longueur -1 ... Une fois que vous avez trouvé Si [x]! = Si + 1 [x], vous pouvez passer à la position suivante x + 1.

Où Si est la vingtième chaîne de la liste. Et [x] est le caractère à la position x.

Answer 2

Un code générique dont les performances sont plutôt médiocres 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

Je ne vois rien de spécialement optimisé.

Vous pouvez faire quelque chose comme ça, ce qui ne devrait pas être trop difficile:

        //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++;
            }
        }

Cela vous donnerait un tableau de caractères identiques à tous les endroits de la liste.

Answer 4

Qu'en est-il de quelque chose comme ça?

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

À la fin de l'exécution, le résultat sera:

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

Answer 5

Voici un algorithme en 5 lignes de 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] }

Mettez ceci dans commonletters.rb. Exemple d'utilisation:

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

En supposant que input.txt contienne:

Toby
Tiny
Tory
Tily

Cela devrait fonctionner avec toutes les entrées que vous lui lancez. Si le fichier en entrée est vide, il se cassera, mais vous pouvez probablement résoudre le problème vous-même. Ceci est O (n) (n est le nombre total de caractères dans l'entrée).

Answer 6

Et voici une version triviale en 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)]

Quelles impressions:

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

Éditer: Voici une version améliorée qui ne nécessite pas de créer une liste (potentiellement) énorme de n-uplets:

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

#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 8

Dans lisp:

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

Il suffit de passer dans les chaînes:

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

Si vous voulez les personnages eux-mêmes:

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)

Si vous ne vous souciez pas des positions, et que vous voulez juste une liste des caractères communs:

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

J'admets que ce n'était pas un algorithme ... juste un moyen de le faire en lisp en utilisant les fonctionnalités existantes

Si vous vouliez le faire manuellement, comme on l'a dit, vous comparez en boucle tous les caractères d'un index donné. Si tous correspondent, enregistrez le caractère correspondant.