Problème d'algorithme: combinaisons de lettres
https://stackoverflow.com/questions/102468
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'essaie d'écrire un morceau de code qui fera ce qui suit:
Prenez les chiffres de 0 à 9 et attribuez une ou plusieurs lettres à ce nombre. Par exemple:
0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G
Lorsque j'ai un code tel que 0123, il est facile de l'encoder. Ce sera évidemment le code NLTD. Quand un nombre comme 5,6 ou 8 est introduit, les choses changent. Un nombre tel que 051 aurait plus d’une possibilité:
NVL et NFL
Il devrait être évident que cela devient encore "pire". avec des nombres plus longs comportant plusieurs chiffres tels que 5,6 ou 8.
Étant assez mauvais en mathématiques, je n’ai pas encore été en mesure de proposer une solution décente qui me permettra de donner au programme beaucoup de chiffres et de le faire cracher toutes les combinaisons de lettres possibles. Donc, j'aimerais avoir de l'aide, parce que je n'arrive pas à comprendre. Découvrez des informations sur les permutations et les combinaisons, mais pas de chance.
Merci pour vos suggestions / indices. Le langage dont j'ai besoin pour écrire le code est PHP, mais toute suggestion générale serait très appréciée.
Mise à jour:
Un peu plus d’arrière-plan: (et merci beaucoup pour les réponses rapides!)
L’idée de ma question est de créer un script qui aide les utilisateurs à convertir facilement les nombres qu’ils souhaitent mémoriser en mots bien plus faciles à retenir. Ceci est parfois appelé "pseudo-numérologie".
Je souhaite que le script me donne toutes les combinaisons possibles, qui sont ensuite bloquées dans une base de données de mots supprimés. Ces mots dépouillés viennent d'un dictionnaire et ont toutes les lettres que j'ai mentionnées dans ma question. De cette manière, le numéro à encoder peut généralement être facilement associé à un ou plusieurs enregistrements de base de données. Et quand cela se produit, vous vous retrouvez avec une liste de mots que vous pouvez utiliser pour vous rappeler le nombre que vous vouliez retenir.
La solution
La structure générale dans laquelle vous souhaitez conserver votre numéro - > assignations de lettres est un tableau ou des tableaux, semblable à:
// 0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z,
// 8 = H or CH or J, 9 = G
$numberMap = new Array (
0 => new Array("N"),
1 => new Array("L"),
2 => new Array("T"),
3 => new Array("D"),
4 => new Array("R"),
5 => new Array("V", "F"),
6 => new Array("B", "P"),
7 => new Array("Z"),
8 => new Array("H", "CH", "J"),
9 => new Array("G"),
);
Ensuite, un peu de logique récursive nous donne une fonction similaire à:
function GetEncoding($number) {
$ret = new Array();
for ($i = 0; $i < strlen($number); $i++) {
// We're just translating here, nothing special.
// $var + 0 is a cheap way of forcing a variable to be numeric
$ret[] = $numberMap[$number[$i]+0];
}
}
function PrintEncoding($enc, $string = "") {
// If we're at the end of the line, then print!
if (count($enc) === 0) {
print $string."\n";
return;
}
// Otherwise, soldier on through the possible values.
// Grab the next 'letter' and cycle through the possibilities for it.
foreach ($enc[0] as $letter) {
// And call this function again with it!
PrintEncoding(array_slice($enc, 1), $string.$letter);
}
}
Trois acclamations pour la récursion! Ceci serait utilisé via:
PrintEncoding(GetEncoding("052384"));
Et si vous le voulez vraiment sous forme de tableau, jouez avec la mise en mémoire tampon de sortie et explosez-la avec "& n; \ n". comme votre chaîne divisée.
Autres conseils
Cela peut être fait facilement de manière récursive.
L’idée est que pour traiter tout le code de taille n, vous devez d’abord traiter les n - 1 chiffres. Une fois que vous avez toutes les réponses pour n-1 chiffres, les réponses pour le tout sont déduites en leur ajoutant le ou les caractères corrects pour le dernier.
Il existe en réalité une bien meilleure solution que d’énumérer toutes les traductions possibles d’un nombre et de les rechercher: effectuez simplement le calcul inverse sur chaque mot de votre dictionnaire et stockez la chaîne de chiffres dans un autre champ. Donc, si votre mapping est:
0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G
votre mappage inverse est:
N = 0,
L = 1,
T = 2,
D = 3,
R = 4,
V = 5,
F = 5,
B = 6,
P = 6,
Z = 7,
H = 8,
J = 8,
G = 9
Notez qu'il n'y a pas de correspondance pour "ch", car le "c" sera supprimé et le "h" sera converti en 8. Quoi qu'il en soit.
Ensuite, tout ce que vous avez à faire est de parcourir chaque lettre du mot du dictionnaire, de saisir le chiffre approprié s'il existe une correspondance et de ne rien faire s'il n'y en a pas.
Stockez toutes les chaînes de chiffres générées dans un autre champ de la base de données. Lorsque vous souhaitez effectuer une recherche, effectuez simplement une requête sur le nombre saisi au lieu de devoir effectuer des dizaines (ou des centaines, voire des milliers) de recherches de mots potentiels.
Ce type de problème est généralement résolu avec la récursivité. En ruby, une solution (rapide et sale) serait
@values = Hash.new([])
@values["0"] = ["N"]
@values["1"] = ["L"]
@values["2"] = ["T"]
@values["3"] = ["D"]
@values["4"] = ["R"]
@values["5"] = ["V","F"]
@values["6"] = ["B","P"]
@values["7"] = ["Z"]
@values["8"] = ["H","CH","J"]
@values["9"] = ["G"]
def find_valid_combinations(buffer,number)
first_char = number.shift
@values[first_char].each do |key|
if(number.length == 0) then
puts buffer + key
else
find_valid_combinations(buffer + key,number.dup)
end
end
end
find_valid_combinations("",ARGV[0].split(""))
Et si vous exécutez ceci à partir de la ligne de commande, vous obtiendrez:
$ ruby r.rb 051
NVL
NFL
Ceci est lié à la recherche par force brute et revenir en arrière
Voici une solution récursive en Python.
#!/usr/bin/env/python
import sys
ENCODING = {'0':['N'],
'1':['L'],
'2':['T'],
'3':['D'],
'4':['R'],
'5':['V', 'F'],
'6':['B', 'P'],
'7':['Z'],
'8':['H', 'CH', 'J'],
'9':['G']
}
def decode(str):
if len(str) == 0:
return ''
elif len(str) == 1:
return ENCODING[str]
else:
result = []
for prefix in ENCODING[str[0]]:
result.extend([prefix + suffix for suffix in decode(str[1:])])
return result
if __name__ == '__main__':
print decode(sys.argv[1])
Exemple de sortie:
$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']
Pourriez-vous faire ce qui suit: Créez un tableau de résultats. Créez un élément dans le tableau avec la valeur ""
"Parcourez les chiffres, par exemple 051, en les analysant individuellement.
Chaque fois qu'une correspondance 1 à 1 entre un nombre est trouvée, ajoutez la valeur correcte à tous les éléments du tableau de résultats. Donc " " devient N.
Chaque fois qu'une correspondance de 1 à plusieurs est trouvée, ajoutez de nouvelles lignes au tableau de résultats avec une option et mettez à jour les résultats existants avec l'autre option. Donc, N devient NV et un nouvel élément est créé NF
Ensuite, le dernier nombre est une correspondance 1 pour 1 afin que les éléments du tableau de résultats deviennent NVL et NFL
Pour produire les résultats en boucle dans le tableau de résultats, en les imprimant, etc.
Soit p une liste de toutes les combinaisons de lettres possibles d'une chaîne numérique s jusqu'au n ème chiffre.
Ensuite, l'algorithme suivant générera p :
digit = s[n+1];
foreach(letter l that digit maps to)
{
foreach(entry e in p(n))
{
newEntry = append l to e;
add newEntry to p(n+1);
}
}
La première itération est un cas un peu spécial, car p -1 n'est pas défini. Vous pouvez simplement initialiser p 0 en tant que liste de tous les caractères possibles pour le premier caractère.
Ainsi, votre exemple 051:
Itération 0:
p(0) = {N}
Itération 1:
digit = 5
foreach({V, F})
{
foreach(p(0) = {N})
{
newEntry = N + V or N + F
p(1) = {NV, NF}
}
}
Itération 2:
digit = 1
foreach({L})
{
foreach(p(1) = {NV, NF})
{
newEntry = NV + L or NF + L
p(2) = {NVL, NFL}
}
}
Le formulaire que vous voulez est probablement quelque chose comme:
function combinations( $str ){
$l = len( $str );
$results = array( );
if ($l == 0) { return $results; }
if ($l == 1)
{
foreach( $codes[ $str[0] ] as $code )
{
$results[] = $code;
}
return $results;
}
$cur = $str[0];
$combs = combinations( substr( $str, 1, $l ) );
foreach ($codes[ $cur ] as $code)
{
foreach ($combs as $comb)
{
$results[] = $code.$comb;
}
}
return $results;}
C’est moche, pidgin-php, veuillez donc le vérifier au préalable. L'idée de base est de générer chaque combinaison de la chaîne à partir de [1..n], puis de faire précéder chaque combinaison de chaque code possible pour str [0]. Gardez à l'esprit que, dans le pire des cas, la longueur de votre chaîne sera exponentielle en termes de performances, car cette ambiguïté est en réalité présente dans votre schéma de codage.
L'astuce consiste non seulement à générer toutes les combinaisons de lettres possibles correspondant à un numéro, mais également à sélectionner la séquence de lettres la plus facile à mémoriser. Une suggestion serait d'exécuter l'algorithme soundex sur chacune des séquences et d'essayer de les faire correspondre à une séquence. Dictionnaire de langue anglaise tel que Wordnet pour rechercher les séquences les plus "sonores en termes réels".
