Как сформировать список всех возможных алфавитных комбинаций на основе ввода чисел
Я только что натолкнулся на интересный вопрос стиля интервью, который я не мог придумать.
В основном, задано число для сопоставления алфавита, так что [1:A, 2:B, 3:C ...]распечатайте все возможные комбинации.
Например, "123" будет генерировать [ABC, LC, AW] так как это может быть разделено на 12,3 и 1,23.
Я думаю, что это должна быть какая-то рекурсивная функция, в которой она проверяет окна размером 1 и 2 и добавляет к предыдущему результату правильное сопоставление букв.
Если кто-то может сформулировать какой-нибудь псевдо /python-код, это будет высоко ценится.
6 ответов
Так же просто, как дерево
Предположим, у вас есть "1261"
Построить дерево с ним Корень.
Определив узел (слева, справа), где слева всегда прямая карта, а справа комбо
Версия предположим, если вы берете данный номер как 1261
1261 ->
(1 (261), 12 (61)) -> 1 - левый узел (прямая карта -> a) 12 - правый узел (combo-map1,2-> L)
(А (261), L (61)) ->
(A (2 (61), 26 (1))), L (6 (1)) ->
(A (B (6 (1)), Z (1)), L (F (1))) ->
(A (B (F (1)), Z (A)), L (F (A))) ->
(A (B (F (A)), Z (A)), L (F (A)))
так что теперь у вас есть весь листовой узел..
просто напечатайте все пути от корневого до конечного узла, это даст вам все возможные комбинации.
как в этом случае
ABFA, AZA, LFA
Поэтому, как только вы закончите построение дерева, просто распечатайте все пути от корня до узла
что ваше требование
Поэтому мне удалось взломать ответ, он не такой питонический, как хотелось бы, и могут быть некоторые избыточности, но он работает с примером 123 для вывода ABC,AW и LC.
Я, вероятно, уберу это завтра (или если кто-то захочет убрать это), просто отправлю это в случае, если кто-то также работает над этим и задается вопросом.
def num_to_alphabet(numbers, ans = ""):
if not numbers:
print ans
numbers = str(numbers)
window = numbers[:2]
alph = string.uppercase
ans = ans[:]
ans2 = ans[:]
window_val = ""
try:
if window[0]:
val = int(numbers[0])-1
if alph[val]:
ans += alph[val]
num_to_alphabet(numbers[1:], ans)
if window[1]:
val = int(window) -1
if alph[val]:
ans2 += alph[val]
if len(window) > 1:
num_to_alphabet(numbers[2:],ans2)
else:
num_to_alphabet(numbers[1:],ans2)
except IndexError:
pass
charMap = {'1':'A', '2':'B' ... }
def getNodes(str):
results = []
if len(str) == 0: return results
c = str[0]
results.append(c)
results = results.join(c.join(getNodes(str[1:])))
if str[:2] in charMap.keys(): results = results.join(c.join(getNodes(str[2:])))
return results
def mapout(nodes):
cArray = []
for x in nodes:
cx = ''
for y in x:
cx = cx + charMap.get(y)
cArray.append(cx)
return cArray
res = getNodes('12345')
print(mapout(res))
Не проверено, но я считаю, что это соответствует тому, что вы ищете.
Итак, я тоже хотел заняться этим, поскольку это действительно крутая проблема. Итак, вот мое решение:
Если мы пока игнорируем переводы на строки, мы, по сути, ищем разбиения набора. Так что для ввода 123 у нас есть набор {1, 2, 3} и ищем перегородки. Но из этих разделов интересны только те, которые поддерживают первоначальный порядок ввода. Таким образом, мы на самом деле не говорим о наборе в конце (где порядок не имеет значения).
Во всяком случае, я назвал это "упорядоченным разделом" - я не знаю, существует ли на самом деле термин для него. И мы можем легко сгенерировать эти упорядоченные разделы, используя рекурсию:
def orderedPartitions(s):
if len(s) == 0:
yield []
return
for i in range(1, len(s)+1):
for p in orderedPartitions(s[i:]):
yield [s[:i]] + p
Для ввода строки '123'это дает нам следующие разделы, и это именно то, что мы ищем:
['1', '2', '3']
['1', '23']
['12', '3']
['123']
Теперь, чтобы вернуться к исходной проблеме, которая требует перевода в строки, все, что нам нужно сделать, это проверить каждый из этих разделов, если они содержат только допустимые числа, то есть от 1 до 26. И если это так, перевести эти числа и вернуть полученную строку.
import string
def alphaCombinations(s):
for partition in orderedPartitions(str(s)):
# get the numbers
p = list(map(int, partition))
# skip invalid numbers
if list(filter(lambda x: x < 1 or x > 26, p)):
continue
# yield translated string
yield ''.join(map(lambda i: string.ascii_uppercase[i - 1], p))
И это работает:
>>> list(alphaCombinations(123))
['ABC', 'AW', 'LC']
>>> list(alphaCombinations(1234))
['ABCD', 'AWD', 'LCD']
>>> list(alphaCombinations(4567))
['DEFG']
Следующий ответ рекурсивно пробует все возможности в текущей позиции (их больше двух!) И продолжается до конца строки. Вот и все.
from string import ascii_uppercase
def alpha_combinations(s):
if len(s) == 0:
yield ""
return
for size in range(1, len(s) + 1):
v = int(s[:size])
if v > 26:
break
if v > 0:
c = ascii_uppercase[v - 1]
for ac in alpha_combinations(s[size:]):
yield c + ac
print(list(alpha_combinations(input())))
Ожидается число в виде строки. Это дает правильный вывод для 101010 (['AAJ', 'AJJ', 'JAJ', 'JJJ']). (Я думаю, что некоторые другие решения неправильно обрабатывают нули.)
Я все еще не уверен в описании, но этот скрипт Python сначала разбивает num на его 'breaks', а затем пробует каждый элемент break в целом как индекс на соответствующий ему символ; затем преобразует каждую цифру члена в буквы слова. Оба вклада показаны перед отображением суммы всех преобразований в буквы / слова для числа "123".
>>> import string
>>> mapping ={str(n):ch for n,ch in zip(range(1,27), string.ascii_uppercase)}
>>> num = '123'
>>> [[num[:i], num[i:]] for i in range(len(num)+1)]
[['', '123'], ['1', '23'], ['12', '3'], ['123', '']]
>>> breaks = set(part for part in sum(([num[:i], num[i:]] for i in range(len(num)+1)), []) if part)
>>> breaks
{'123', '12', '3', '1', '23'}
>>> as_a_whole = [mapping[p] for p in breaks if p in mapping]
>>> as_a_whole
['L', 'C', 'A', 'W']
>>> by_char = [''.join(mapping[n] for n in p) for p in breaks]
>>> by_char
['ABC', 'AB', 'C', 'A', 'BC']
>>> everything = sorted(set(as_a_whole + by_char))
>>> everything
['A', 'AB', 'ABC', 'BC', 'C', 'L', 'W']
>>>