0

我必须生成代表电话中数字序列的所有可能的字母组合......例如：如果条目是“423”，则输出应该是：

GAD   GAE   GAF   GBD   GBE   GBF   GCD   GCE   GCF    
HAD   HAE   HAF   HBD   HBE   HBF   HCD   HCE   HCF   
IAD   IAE   IAF   IBD   IBE   IBF   ICD   ICE   ICF

我必须使用递归来解决这个问题......我开始使用这样的字典：

dic = {'2' : 'ABC', '3' : 'DEF', '4' : 'GHI', '5' : 'JKL', '6' : 'MNO', '7' : 'PQRS',     '8' : 'TUV', '9' : 'WXYZ'}

但我不知道如何在这里使用递归......有人可以帮忙吗？

我想这样开始：

def telephoneSequence(str):
    for i in range (len(str)):
        return dic[str[i]]
4

3 回答 3

10

我想你正在寻找itertools.product：

>>> import itertools
>>> list(itertools.product('GHI','ABC','DEF'))
[('G', 'A', 'D'), ('G', 'A', 'E'), ('G', 'A', 'F'), ('G', 'B', 'D'), ('G', 'B', 'E'), ('G', 'B', 'F'), ('G', 'C', 'D'), ('G', 'C', 'E'), ('G', 'C', 'F'), ('H', 'A', 'D'), ('H', 'A', 'E'), ('H', 'A', 'F'), ('H', 'B', 'D'), ('H', 'B', 'E'), ('H', 'B', 'F'), ('H', 'C', 'D'), ('H', 'C', 'E'), ('H', 'C', 'F'), ('I', 'A', 'D'), ('I', 'A', 'E'), ('I', 'A', 'F'), ('I', 'B', 'D'), ('I', 'B', 'E'), ('I', 'B', 'F'), ('I', 'C', 'D'), ('I', 'C', 'E'), ('I', 'C', 'F')]

这给了你一堆元组，但你可以''.join很容易地做到。

>>> list(''.join(p) for p in itertools.product('GHI','ABC','DEF'))
['GAD', 'GAE', 'GAF', 'GBD', 'GBE', 'GBF', 'GCD', 'GCE', 'GCF', 'HAD', 'HAE', 'HAF', 'HBD', 'HBE', 'HBF', 'HCD', 'HCE', 'HCF', 'IAD', 'IAE', 'IAF', 'IBD', 'IBE', 'IBF', 'ICD', 'ICE', 'ICF']

当然，这不是递归的，如果您有其他约束力（也许是教授？），也不会帮助您。我留下这个答案是为了证明 python 标准库是多么强大，并表明递归确实不是解决这类问题的最佳工具（至少在 python 中不是）。

于 2013-02-18T13:31:23.563 回答
4

如果您不想使用 itertools.product 并递归实现它，您可以执行以下操作：

d = { 
    '0': "0",
    '1': "1",
    '2': "ABC",
    '3': "DEF",
    '4': "GHI",
    '5': "JKL",
    '6': "MNO",
    '7': "PQRS",
    '8': "TUV",
    '9': "WXYZ",
}

def permutatePhoneNum(number):
    result = []
    if len(number) == 1:
        return [i for i in d[number]]
    restPerm = permutatePhoneNum(number[1:])
    for chr in d[number[0]]:
        for rest in restPerm:
            result.append(chr + rest)
    return result

然后，您可以按以下方式使用它：

>>> permutatePhoneNum("423")
['GAD', 'GAE', 'GAF', 'GBD', 'GBE', 'GBF', 'GCD', 'GCE', 'GCF', 'HAD', 'HAE', 
'HAF', 'HBD', 'HBE', 'HBF', 'HCD', 'HCE', 'HCF', 'IAD', 'IAE', 'IAF', 'IBD', 
'IBE', 'IBF', 'ICD', 'ICE', 'ICF']
于 2013-02-18T13:34:16.150 回答
0

仅限于使用递归比我预期的要正确 - 有点不切实际，因为 Python 有几个有用的内置函数可以让做这些事情变得相当容易。但是，FWIW，这里是：

KEYPAD = {
    '0': '0',   '1': '1',   '2': 'ABC',  '3': 'DEF', '4': 'GHI',
    '5': 'JKL', '6': 'MNO', '7': 'PQRS', '8': 'TUV', '9': 'WXYZ',
}

def teleseq(digits, letters=[], result=None):
    if result is None: result = []
    if len(digits) == 1:
        result.extend(''.join(letters+[letter]) for letter in KEYPAD[digits[0]])
    else:
        for letter in KEYPAD[digits[0]]:
            teleseq(digits[1:], letters+[letter], result)
    return result

print sorted(teleseq('432'))

输出：

['GDA', 'GDB', 'GDC', 'GEA', 'GEB', 'GEC', 'GFA', 'GFB', 'GFC', 'HDA', 'HDB',
 'HDC', 'HEA', 'HEB', 'HEC', 'HFA', 'HFB', 'HFC', 'IDA', 'IDB', 'IDC', 'IEA',
 'IEB', 'IEC', 'IFA', 'IFB', 'IFC']
于 2013-02-18T18:42:28.913 回答