Проблема алгоритма: буквенные комбинации

Question

Я пытаюсь написать кусок кода, который будет делать следующее:

Возьмите цифры от 0 до 9 и присвойте одну или несколько букв этому номеру. Например:

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

Когда у меня есть код, такой как 0123, его легко кодировать. Это, очевидно, будет составлять код NLTD. Когда вводится такое число, как 5,6 или 8, все становится иначе. Число, подобное 051, приведет к более чем одной возможности:

NVL и NFL

Должно быть очевидно, что это становится еще «хуже» с более длинными числами, которые включают несколько цифр, таких как 5,6 или 8.

Будучи довольно плохо разбирающимся в математике, я пока не смог придумать достойного решения, которое позволило бы мне набрать в программе кучу цифр и заставить ее выплевывать все возможные комбинации букв. Так что я хотел бы помочь с этим, потому что я не могу понять это. Откопал немного информации о перестановках и комбинациях, но не повезло.

Спасибо за любые предложения / подсказки. Язык, на котором мне нужно написать код, - это PHP, но любые общие советы будут высоко оценены.

Обновление:

Еще немного предыстории: (и большое спасибо за быстрый ответ!)

Идея, лежащая в основе моего вопроса, состоит в том, чтобы создать скрипт, который поможет людям легко преобразовывать числа, которые они хотят запомнить, в слова, которые гораздо легче запомнить. Это иногда называют «псевдо-нумерологией».

Я хочу, чтобы скрипт дал мне все возможные комбинации, которые затем сопоставляются с базой данных раздетых слов. Эти раздетые слова просто взяты из словаря, и из них удалены все буквы, которые я упомянул в своем вопросе. Таким образом, число, которое должно быть закодировано, обычно может быть легко связано с одной или несколькими записями базы данных. И когда это происходит, вы получаете список слов, которые вы можете использовать, чтобы запомнить число, которое вы хотели запомнить.

Answer 1

Это можно легко сделать рекурсивно.

Идея состоит в том, что для обработки всего кода размера n вы должны сначала обработать n - 1 цифру. Когда у вас есть все ответы для n-1 цифр, ответы для целых выводятся путем добавления к ним правильных символов для последней.

Answer 2

На самом деле есть гораздо лучшее решение, чем перечислять все возможные переводы числа и искать их: просто выполните обратное вычисление для каждого слова в вашем словаре и сохраните строку цифр в другом поле. Так что если ваше отображение:

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

Ваше обратное отображение:

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

Обратите внимание, что для 'ch' нет сопоставления, потому что 'c' будет удалено, а 'h' будет преобразовано в 8 в любом случае.

Затем все, что вам нужно сделать, - это перебирать каждую букву в словарном слове, выводить соответствующую цифру, если есть совпадение, и ничего не делать, если ее нет.

Сохранить все сгенерированные строки цифр как другое поле в базе данных. Если вы хотите что-то найти, просто выполните простой запрос для введенного числа вместо того, чтобы выполнять десятки (или сотни, или тысячи) поисков потенциальных слов.

Answer 3

Подобные проблемы обычно решаются с помощью рекурсии. В ruby ​​одно (быстрое и грязное) решение будет

@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(""))

И если вы запустите это из командной строки, вы получите:

$ ruby r.rb 051
NVL
NFL

Это связано с перебором и возвратом

Answer 4

Общая структура, в которой вы хотите хранить свой номер -> буквенные присвоения, представляет собой массив или массивы, подобные:

// 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"),
);

Затем немного рекурсивной логики дает нам функцию, похожую на:

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

Три ура за рекурсию! Это будет использоваться через:

PrintEncoding(GetEncoding("052384"));

А если вы действительно хотите использовать его как массив, поиграйте с буферизацией вывода и взорвитесь, используя "\ n" в качестве разделенной строки.

Answer 5

Вот рекурсивное решение в 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])

Пример вывода:

$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']

Answer 6

Хитрость заключается не только в том, чтобы сгенерировать все возможные комбинации букв, которые соответствуют заданному числу, но и в выборе последовательности букв, которую легче всего запомнить. Было бы предложено запустить алгоритм soundex для каждой последовательности и попытаться сопоставить его со словарем английского языка, таким как Wordnet , чтобы найти наиболее «звучащие» последовательности .

Answer 7

Форма, которую вы хотите, вероятно, выглядит примерно так:

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

Это ужасно, pidgin-php, поэтому, пожалуйста, сначала проверьте это. Основная идея состоит в том, чтобы сгенерировать каждую комбинацию строки из [1..n] и затем добавить перед всеми этими комбинациями перед каждым возможным кодом для str [0]. Имейте в виду, что в худшем случае это будет иметь экспоненциальную производительность по длине вашей строки, потому что такая большая неопределенность фактически присутствует в вашей схеме кодирования.

Answer 8

Позвольте p<sub>n</sub> быть списком всех возможных комбинаций букв данной строки чисел s до цифры n<sup>th</sup>.

Тогда следующий алгоритм сгенерирует p<sub>n+1</sub>:

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

Первая итерация представляет собой особый случай, поскольку p _-1 не определено. Вы можете просто инициализировать p ₀ как список всех возможных символов для первого символа.

Итак, ваш пример 051:

Итерация 0:

p(0) = {N}

Итерация 1:

digit = 5
foreach({V, F})
{
    foreach(p(0) = {N})
    {
        newEntry = N + V  or  N + F
        p(1) = {NV, NF}
    }
}

Итерация 2:

digit = 1
foreach({L})
{
    foreach(p(1) = {NV, NF})
    {
        newEntry = NV + L  or  NF + L
        p(2) = {NVL, NFL}
    }
}

Answer 9

Не могли бы вы сделать следующее: Создайте массив результатов. Создать элемент в массиве со значением ""

Переберите числа, скажем, 051, анализируя каждое из них в отдельности.

Каждый раз, когда найдено 1 к 1 совпадение числа, добавьте правильное значение ко всем элементам в массиве результатов. Так что "" становится N.

Каждый раз, когда найдено соответствие 1 ко многим, добавьте новые строки в массив результатов с одним параметром и обновите существующие результаты с другим параметром. Таким образом, N становится NV, и создается новый элемент NF

Тогда последнее число соответствует 1: 1, поэтому элементы в массиве результатов становятся NVL и NFL

Для создания цикла результатов по массиву результатов, его печати или чего-либо еще.