Алгоритм поиска слов, написанных по цифре

Question

Я пытаюсь найти способ определить все возможные слова, которые можно записать заданным числом, учитывая сопоставление алфавитов со значениями.

В конечном итоге я хочу найти решение, которое работает для любого сопоставления 1- или 2-значных значений буквы, но для иллюстрации предположим, что A=1, B=2,...Z=26.

Пример: 12322 может быть равно abcbb (1,2,3,2,2), lcbb (12,3,2,2), awbb (1,23,2,2), abcv (1,2,3,22), awv (1,23,22), или lcv (12,3,22).

---

Вот о чем я подумал до сих пор:

Я построю дерево всех возможных слов, используя число.

Для этого я начну с дерева с одним корневым узлом и фиктивными данными.

Затем я разберу число по цифрам, начиная с младшей значащей цифры.

На каждом шаге я беру последнюю цифру оставшейся части числа и вставляю ее в левое поддерево текущего узла и удаляю эту цифру из числа левого поддерева этого узла.Затем для того же узла я проверю, образуют ли предыдущие ДВЕ цифры действительный алфавит, и если да, то я помещу их в правое поддерево (и удалю 2 цифры из числа правого поддерева этого узла).

Затем я повторю описанные выше шаги рекурсивно для каждого узла, используя оставшуюся часть числа, пока не останется цифр.

Чтобы проиллюстрировать, для 12322 мое дерево будет выглядеть примерно так:

                *
             /     \
            /       \
           2         22
         /         /   \
        2         3     23
      /   \      / \    /
    3      23   2   12 1
   / \    /    /
  2   12 1    1
 /
1 

Чтобы получить слова, я пройду все возможные пути от листьев к узлам.

---

Кажется, это слишком сложное решение для довольно простой проблемы, и я пытаюсь найти более простой способ решить эту проблему.

Answer 1

Предположим, у вас уже есть все возможные комбинации [2, 3, 2, 2] , какова будет комбинация [1, 2, 3, 2, 2] (добавить [1] в голову)? Это не сложно, вывести это должно быть:

  A1: put [1] to the head of all_the_combinations_of[1,2,3,2,2] and 
  A2: put [1*10 + 2] to the head of all_the_combinations_of[2,3,2,2] if [1*10 + 2 <=26]

Как только мы получим это, следующее будет легко. Я реализовал версию Ruby с трассировкой отказов для вашей справки.

def comb a
    c = []
    puts a.inspect
    return [a] if a.length <= 1

    c =  comb(a[1..-1]).map {|e| [a[0]] + e}
    if a[0] * 10 + a[1] <= 26
            c += comb(a[2..-1]).map { |f| [a[0] * 10 + a[1]] + f }
    end
    c
end

h = Hash[*(1..26).to_a.zip(('A'..'Z').to_a).flatten]
#h.keys.sort.each {|k| puts "#{k}=>#{h[k]}"}

comb([1,2,3,2,2]).each do |comb|
    puts comb.map {|k| h[k]}.join
end

[1, 2, 3, 2, 2]
  A1 [2, 3, 2, 2]
      [3, 2, 2]
         [2, 2]
            [2]
             []
      [2, 2]
         [2]
          []
  A2 [3, 2, 2]
      [2, 2]
         [2]
          []
ABCBB
ABCV
AWBB
AWV
LCBB
LCV

Answer 2

На самом деле вам не нужно строить дерево - просто рекурсивно.

<Ол>

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

Когда мы вернемся из рекурсии, попробуйте добавить еще одну цифру (если мы были 1 или 2 ранее) и повторить рекурсию.

Answer 3

Решением для перебора было бы динамическое заполнение массива от 1 до N, где элемент a [i] содержит набор строк, которые образуют a [1] a [2 ] a [3] ... a [i] после расширения. Вы можете заполнить [1] с нуля, а затем заполнить a [2] , основываясь на наборе a [1] и втором символе в строке. Затем вы заполняете [3] и т. Д. На каждом участке вы должны только оглянуться назад на a [i-1] и a [i-2] (и на s [i-1] и s [i] , где s - ваша числовая последовательность).

Наконец, после того как вы заполните a [n] , он будет содержать ответ.

Для примера '12322' последовательность становится такой:

a[1] = { "a" }
a[2] = { a + 'b' | a in a[1] } union { "l" } = { "ab", "l" }
a[3] = { a + 'c' | a in a[2] } union { a + 'w' | a in a[1] } = { "abc", "lc", "aw" }
a[4] = { a + 'b' | a in a[3] } union { } = { "abcb", "lcb", "awb" }
a[5] = { a + 'b' | a in a[4] } union { a + 'v' | a in a[3] } = { "abcbb", "lcbb", "awbb", "abcv", "lcv", "awv" }

По сути, это версия динамического программирования рекурсивного решения, приведенного выше.

Answer 4

Альтернативный способ сделать это — обратить проблему вспять:

• Учитывая словарь слов, вычислите числовые строки, которые будут сгенерированы, и сохраните эти данные в структуре карты/словаря, т.е.таблица['85'] = 'привет'
• Для каждой из первых x цифр числа, которое вы ищете, посмотрите, есть ли оно в таблице, т.е.table.ContainsKey('1'), table.ContainsKey('12'), ...
• Если вы пытаетесь найти последовательность слов, сгенерируйте слова, которые начинаются в каждом месте числовой строки, а затем выполните рекурсивный поиск, чтобы найти все фразы из нее.