Algorithmus Ausgabe: Buchstabenkombinationen
https://stackoverflow.com/questions/102468
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, ein Stück Code zu schreiben, der die folgenden tun:
Nehmen Sie die Zahlen 0 bis 9 und einen oder mehr Buchstaben auf diese Nummer zuweisen. Zum Beispiel:
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
Wenn ich einen Code wie 0123 haben, ist es eine einfache Aufgabe, sie zu kodieren. Es wird offensichtlich den Code NLTD bilden. Wenn eine Zahl wie 5,6 oder 8 eingeführt wird, werden die Dinge anders. Eine Zahl wie 051 in mehr als eine Möglichkeit ergeben würde:
NVL und NFL
Es sollte klar sein, dass dies wird noch „schlechter“ mit mehr Zahlen, die mehrere Ziffern wie 5,6 oder 8 enthalten.
Als in Mathematik ziemlich schlecht, ich habe noch nicht gelungen, mit einer guten Lösung zu kommen, die mir erlauben, dem Programm eine Reihe von Zahlen zu füttern und haben es alle möglichen Buchstabenkombinationen ausspucken. Also würde ich etwas Hilfe mit ihm lieben, denn ich kann nicht auf einen Reim scheint aus. Dug einige Informationen über Permutationen und Kombinationen, aber kein Glück.
Vielen Dank für alle Anregungen / Hinweise. Die Sprache muss ich den Code schreiben, in PHP, aber keine allgemeine Hinweise sehr geschätzt werden würde.
Update:
etwas mehr Hintergrund: (! Und vielen Dank für die schnellen Antworten)
Die Idee hinter meiner Frage ist, ein Skript zu erstellen, die Menschen helfen, auf einfache Weise Zahlen konvertieren sie zu Worten erinnern wollen, die viel leichter in Erinnerung bleiben. Dies wird manchmal als „pseudo-Numerologie“.
Ich mag das Skript mir die möglichen Kombinationen, alles zu geben, die dann mit einer Datenbank von gestrippt Worten gehalten werden. Diese gestrippt Worte kommen nur aus einem Wörterbuch und haben alle Briefe, die ich in meiner Frage erwähnt aus ihnen abgezogen. Auf diese Weise wird die Anzahl codiert ein eine oder mehrere Datenbankeinträge in der Regel leicht in Beziehung gesetzt werden kann. Und wenn das geschieht, beenden Sie mit einer Liste von Wörtern, die Sie um die Nummer zu erinnern, können Sie sich merken wollen.
Lösung
Die allgemeine Struktur Sie Ihre Nummer halten wollen -> Buchstabenzuweisungen ist ein Array oder Arrays, ähnlich wie:
// 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"),
);
Dann gibt ein bisschen rekursiven Logik uns eine ähnliche Funktion wie:
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);
}
}
Ein dreifaches Hoch für Rekursion! Dies würde über verwendet werden:
PrintEncoding(GetEncoding("052384"));
Und wenn Sie es wirklich als ein Array wollen, mit Ausgabepufferung spielen und mit „\ n“ als Split-String explodiert.
Andere Tipps
Es kann leicht rekursiv durchgeführt werden.
Die Idee ist, dass der gesamte Code der Größe n zu handhaben, müssen Sie zunächst die n behandeln müssen - 1 Ziffern. Wenn Sie alle Antworten für n-1 Ziffern haben, sind die Antworten für die ganze abgeleitet durch das letzte man ihnen die richtige (n) char (n) angehängt wird.
Es gibt tatsächlich eine viel bessere Lösung als alle möglichen Übersetzungen einer Reihe Aufzählen und suchen sie nach oben: einfach die umgekehrte Berechnung tun auf jedes Wort in das Wörterbuch, und speichern Sie die Ziffernfolge in einem anderen Feld. Also, wenn Ihr Mapping ist:
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
Ihr Reverse-Mapping ist:
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
Beachten Sie, es gibt keine Zuordnung für ‚ch‘, weil das ‚c‘ fallen gelassen wird, und die ‚h‘ wird auf 8 ohnehin umgewandelt werden.
Dann alles, was Sie tun müssen, ist in dem Wort aus dem Wörterbuch, Ausgabe der entsprechende Ziffer, wenn es ein Spiel, durch jeden Buchstaben laufen und nichts tun, wenn es nicht.
Speichern Sie alle die generierten Ziffernfolgen als ein anderes Feld in der Datenbank. Wenn Sie auf etwas suchen möchten, führen Sie einfach eine einfache Abfrage für die Nummer eingegeben, statt zehn zu tun (oder Hunderte oder Tausende) von Lookups potentieller Wörtern.
Diese Art von Problem ist in der Regel mit Rekursion gelöst. In Rubin, eine (quick and dirty) Lösung wäre,
@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(""))
Und wenn Sie dies über die Befehlszeile ausführen, erhalten Sie:
$ ruby r.rb 051
NVL
NFL
Dies bezieht sich auf Brute-Force-Suche und Rückzieher
Hier ist eine rekursive Lösung in 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])
Beispiel Ausgabe:
$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']
Könnten Sie wie folgt vor: Erstellen Sie eine Ergebnis-Reihe. Erstellen Sie ein Element im Array mit dem Wert „“
Schleife durch die Zahlen, sagt 051 individuell jeden zu analysieren.
Jedes Mal, wenn eine 1 bis 1 Übereinstimmung zwischen einer Nummer gefunden wird, um den korrekten Wert für alle Elemente in der Ergebnisliste Array hinzufügen. So "" wird N.
Jedes Mal, wenn ein 1 bis viele Übereinstimmung gefunden wird, fügen Sie neue Zeilen in die Ergebnis-Reihe mit einer Option, und aktualisieren Sie die vorhandenen Ergebnisse mit der anderen Option. So N wird NV und ein neues Element NF erstellt
Dann wird die letzte Zahl ist ein 1 zu 1 Spiel, so dass die Elemente in der Ergebnis-Reihe wurden NVL und NFL
Um die Ergebnisse Schleife durch die Ergebnisse Array zu erzeugen, sie zu drucken, oder was auch immer.
Lassen Sie pn eine Liste aller möglichen Buchstabenkombinationen einer bestimmten Zahlenfolge sein s zum nth Ziffer auf.
Dann wird der folgende Algorithmus erzeugt pn+1:
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);
}
}
Die erste Iteration ist so etwas wie ein Sonderfall, da p -1 ist nicht definiert. Sie können einfach initialisieren p 0 als Liste aller möglichen Zeichen für das erste Zeichen.
So, Ihr 051 Beispiel:
Iteration 0:
p(0) = {N}
Iteration 1:
digit = 5
foreach({V, F})
{
foreach(p(0) = {N})
{
newEntry = N + V or N + F
p(1) = {NV, NF}
}
}
Iteration 2:
digit = 1
foreach({L})
{
foreach(p(1) = {NV, NF})
{
newEntry = NV + L or NF + L
p(2) = {NVL, NFL}
}
}
Das Formular, das Sie wollen, ist wahrscheinlich so etwas wie:
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;}
Das ist hässlich, Pidgin-php so bitte überprüfen Sie es zuerst. Die Grundidee ist jede Kombination der Zeichenfolge von [1..n] und dann schreibe an dem vor all diesen Kombinationen jeden möglichen Code für str [0] zu erzeugen. Beachten Sie, dass im schlimmsten Fall diese Leistung exponentiell in der Länge der Zeichenfolge haben wird, denn das ist viel Mehrdeutigkeit tatsächlich in Ihrem Codierungsschema ist.
Der Trick ist, nicht nur alle möglichen Buchstabenkombinationen zu erzeugen, die eine bestimmte Anzahl übereinstimmt, aber die Buchstabenfolge auszuwählen, die meisten leicht zu merken ist. Ein Vorschlag wäre, die soundex Algorithmus auf jeder der Sequenz laufen und versuchen, gegen eine entsprechen Englisch Sprachwörterbuch wie Wordnet das meist ‚echte Wort klingenden‘ finden Sequenzen.
