Algoritmo Issue: combinações de letras
https://stackoverflow.com/questions/102468
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou tentando escrever um pedaço de código que irá fazer o seguinte:
Leve os números de 0 a 9 e atribuir uma ou mais cartas para esse número. Por exemplo:
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
Quando eu tiver um código como 0123, é uma tarefa fácil para codificá-lo. Ele vai, obviamente, fazer o NLTD código. Quando um número como 5,6 ou 8 é introduzido, as coisas ficam diferentes. Um número como 051 resultaria em mais de uma possibilidade:
NVL e NFL
Deveria ser óbvio que este fica ainda "pior" com números mais longos que incluem vários dígitos, como 5,6 ou 8.
Ser muito ruim em matemática, eu ainda não foi capaz de chegar a uma solução decente que permita-me para alimentar o programa um monte de números e tê-lo cuspir todas as possíveis combinações de letras. Então, eu adoraria alguma ajuda com isso, porque eu não consigo descobrir isso. Dug-se algumas informações sobre permutações e combinações, mas sem sorte.
Obrigado por todas as sugestões / pistas. A linguagem que eu preciso escrever o código é PHP, mas as dicas gerais seria muito apreciada.
Update:
Alguns mais fundo: (! E muito obrigado pelas respostas rápidas)
A idéia por trás a minha pergunta é a construção de um script que irá ajudar as pessoas a converter facilmente números que eles querem lembrar-se de palavras que são muito mais fáceis de memorizar. Isto é por vezes referido como "pseudo-numerologia".
Eu quero o script para me dar todas as combinações possíveis que depois são detidos contra um banco de dados de palavras despojado. Estas palavras despojado acabado de chegar de um dicionário e tem todas as letras que eu mencionei na minha pergunta despojado fora delas. Dessa forma, o número a ser codificado geralmente pode ser facilmente relacionado a um ou mais registros de banco de dados. E quando isso acontece, você acaba com uma lista de palavras que você pode usar para lembrar o número que você queria lembrar.
Solução
A estrutura geral que deseja manter o seu número -> atribuições de letra é uma matriz ou matrizes, semelhante a:
// 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"),
);
Em seguida, um pouco de lógica recursiva nos dá uma função semelhante a:
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);
}
}
aplausos Três para recursão! Isto seria usado via:
PrintEncoding(GetEncoding("052384"));
E se você realmente quer que ele como uma matriz, o jogo com o buffer de saída e explodir usando "\ n", como a cadeia de divisão.
Outras dicas
Isso pode ser feito facilmente de forma recursiva.
A idéia é que para lidar com todo o código de tamanho n, você deve lidar com primeiro o n - 1 dígitos. Depois de ter todas as respostas para n-1 dígitos, as respostas para o conjunto são deduzidos, acrescentando-lhes as corretas (s) CHAR (s) para o último.
Na verdade, há uma solução muito melhor do que enumerar todas as possíveis traduções de um número e procurá-las: Basta fazer o cálculo inverso em cada palavra no seu dicionário, e armazenar a seqüência de dígitos em outro campo. Portanto, se seu mapeamento é:
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
o mapeamento inverso é:
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
Note que não há mapeamento para 'ch', porque o 'c' será descartado, e o 'h' será convertido em 8 de qualquer maneira.
Então, tudo que você tem a fazer é iterar através de cada letra da palavra dicionário, saída o dígito apropriado se há um jogo, e não fazer nada se não houver.
loja todas as seqüências de dígitos gerados como outro campo no banco de dados. Quando você quiser procurar alguma coisa, basta executar uma consulta simples para o número inserido, em vez de ter que fazer dezenas (ou centenas, ou milhares) de pesquisas de palavras possíveis.
Este tipo de problema geralmente são resolvidos com recursividade. Em Ruby, uma solução (rápido e sujo) seria
@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(""))
E se você executar este a partir da linha de comando que você vai ter:
$ ruby r.rb 051
NVL
NFL
Isso está relacionado à pesquisa brute-force e retrocesso
Aqui está uma solução recursiva em 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])
Exemplo de saída:
$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']
Você pode fazer o seguinte: Criar uma matriz de resultados. Criar um item na matriz com o valor ""
percorrer os números, dizer 051 analisar cada um individualmente.
Cada vez que um 1 a 1 jogo entre um número é encontrado adicionar o valor correto para todos os itens na matriz resultados. Assim, "" torna-se N.
Cada vez que um 1 a muitos correspondência for encontrada, adicionar novas linhas à matriz resultados com uma opção, e atualizar os resultados existentes com a outra opção. Então N se torna NV e um novo item é criado NF
Em seguida, o último número é um 1 a 1 jogo para que os itens na matriz resultados tornam-se NVL e NFL
Para produzir o loop resultados através da matriz resultados, imprimi-los, ou o que quer.
Let pn ser uma lista de todas as combinações de letras possíveis de uma determinada cadeia número s até o dígito nth.
Então, o seguinte algoritmo irá gerar 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);
}
}
A primeira iteração é um pouco de um caso especial, uma vez que p -1 é indefinido. Você pode simplesmente inicializar p 0 como a lista de todos os caracteres possíveis para o primeiro caractere.
Assim, o 051 exemplo:
A iteração 0:
p(0) = {N}
A iteração 1:
digit = 5
foreach({V, F})
{
foreach(p(0) = {N})
{
newEntry = N + V or N + F
p(1) = {NV, NF}
}
}
Iteração 2:
digit = 1
foreach({L})
{
foreach(p(1) = {NV, NF})
{
newEntry = NV + L or NF + L
p(2) = {NVL, NFL}
}
}
A forma que você quer é provavelmente algo como:
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;}
Esta é feio, pidgin-php por isso, verificar-lo primeiro. A idéia básica é a de gerar todas as combinações da string a partir de [1..n] e, em seguida, preceder à frente de todas essas combinações cada código possível para str [0]. Tenha em mente que, no pior caso isso terá exponencial desempenho no comprimento de sua corda, porque isso muita ambiguidade é realmente presente no seu esquema de codificação.
O truque é não só para gerar todas as combinações de letras possíveis que correspondam a um determinado número, mas para selecionar a seqüência de letras que é mais fácil de lembrar. Uma sugestão seria a de executar o soundex algoritmo em cada um dos seqüência e tentar igualar contra um idioma Inglês dicionário, como Wordnet para encontrar o mais 'real-palavra soando' seqüências.
