Проблема с алгоритмом:буквосочетания
-
01-07-2019 - |
Вопрос
Я пытаюсь написать фрагмент кода, который будет делать следующее:
Возьмите цифры от 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 приведет к более чем одному варианту:
НВЛ и НФЛ
Должно быть очевидно, что ситуация становится еще «хуже» с более длинными числами, состоящими из нескольких цифр, например 5,6 или 8.
Будучи довольно плох в математике, я пока не смог придумать достойного решения, которое позволило бы мне скормить программе кучу чисел и заставить ее выдавать все возможные комбинации букв.Так что мне бы очень хотелось с этим помочь, потому что я, похоже, не могу в этом разобраться.Накопал некоторую информацию о перестановках и комбинациях, но безуспешно.
Спасибо за любые предложения/подсказки.Язык, на котором мне нужно написать код, — PHP, но любые общие подсказки будут высоко оценены.
Обновлять:
Еще немного предыстории:(и большое спасибо за быстрые ответы!)
Идея моего вопроса состоит в том, чтобы создать сценарий, который поможет людям легко преобразовывать числа, которые они хотят запомнить, в слова, которые гораздо легче запомнить.Иногда это называют «псевдонумерологией».
Я хочу, чтобы сценарий предоставил мне все возможные комбинации, которые затем сохраняются в базе данных удаленных слов.Эти вырезанные слова только что взяты из словаря, и из них удалены все буквы, которые я упомянул в своем вопросе.Таким образом, число, которое нужно закодировать, обычно можно легко связать с одной или несколькими записями базы данных.И когда это произойдет, вы получите список слов, которые можно использовать, чтобы запомнить число, которое вы хотели запомнить.
Решение
Общая структура, в которой вы хотите хранить свои числа -> назначения букв, представляет собой массив или массивы, похожие на:
// 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 необходимо сначала обработать n - 1 цифр.Как только у вас есть все ответы для n-1 цифр, ответы для всего числа выводятся путем добавления к ним правильных символов для последнего.
На самом деле есть гораздо лучшее решение, чем перечислять все возможные переводы числа и искать их:Просто выполните обратное вычисление для каждого слова в словаре и сохраните строку цифр в другом поле.Итак, если ваше отображение:
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.
Затем все, что вам нужно сделать, это перебрать каждую букву в словарном слове, вывести соответствующую цифру, если есть совпадение, и ничего не делать, если ее нет.
Сохраните все сгенерированные строки цифр как другое поле в базе данных.Если вы хотите что-то найти, просто выполните простой запрос по введенному числу, вместо того, чтобы выполнять десятки (или сотни, или тысячи) поисков потенциальных слов.
Проблемы такого рода обычно решаются с помощью рекурсии.В 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
Это связано с грубый поиск и возврат назад
Вот рекурсивное решение на 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']
Не могли бы вы сделать следующее:Создайте массив результатов.Создайте элемент в массиве со значением ""
Прокрутите числа, скажем, 051, анализируя каждое из них по отдельности.
Каждый раз, когда обнаруживается совпадение 1 к 1 между числами, добавляйте правильное значение ко всем элементам массива результатов.Итак, "" становится N.
Каждый раз, когда обнаруживается совпадение от 1 ко многим, добавляйте новые строки в массив результатов с помощью одного параметра и обновляйте существующие результаты с помощью другого параметра.Таким образом, N становится NV, и создается новый элемент NF.
Тогда последнее число - это совпадение 1 до 1, поэтому элементы в массиве результатов стали NVL и NFL
Чтобы получить результаты, пройдите через массив результатов, распечатав их или что-то еще.
Позволять pн
быть списком всех возможных комбинаций букв данной числовой строки s
вверх к nй
цифра.
Тогда следующий алгоритм сгенерирует pп+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);
}
}
Первая итерация представляет собой своего рода частный случай, поскольку p-1 является неопределенным.Вы можете просто инициализировать p0 как список всех возможных символов для первого символа.
Итак, ваш пример 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}
}
}
Форма, которая вам нужна, вероятно, выглядит примерно так:
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].Имейте в виду, что в худшем случае производительность будет экспоненциально зависеть от длины вашей строки, потому что в вашей схеме кодирования действительно присутствует большая двусмысленность.
Хитрость заключается не только в том, чтобы сгенерировать все возможные комбинации букв, соответствующие заданному числу, но и выбрать последовательность букв, которую легче всего запомнить.Было бы предложено запустить Саундекс алгоритм для каждой последовательности и попытайтесь сопоставить его со словарем английского языка, например Ворднет чтобы найти последовательности, наиболее «звучащие по-настоящему».