Python的递归

我不得不产生的代表在电话的数列...例如字母所有可能的组合：如果条目是“423”，输出应该是：Python的递归

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]]

来源

2013-02-18 user2083363

开始产生长度为1的条目比问自己怎样才能长1的入口被打开，以长度为2的合法入境。 – StoryTeller 2013-02-18 13:26:04

欢迎来到Stack Overflow！看起来你希望我们为你写一些代码。尽管许多用户愿意为遇险的编码人员编写代码，但他们通常只在海报已尝试自行解决问题时才提供帮助。证明这一努力的一个好方法是包含迄今为止编写的代码，示例输入（如果有的话），期望的输出和实际获得的输出（控制台输出，堆栈跟踪，编译器错误 - 无论是适用）。您提供的细节越多，您可能会收到的答案就越多。 – 2013-02-18 13:27:09

@ user2083363，不要在评论中发布代码。编辑您的问题并将代码添加到它。 – StoryTeller 2013-02-18 13:30:43

我认为你正在寻找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-18 13:31:23 mgilson

这将是敏感的解决方案，但OP说他必须使用递归... – 2013-02-18 13:34:04

哦，对，我错过了递归部分...那么，也许这对没有这种限制的人会有用。 – mgilson 2013-02-18 13:35:06

或检查他的结果是否正确。 – MatthieuW 2013-02-18 15:27:51

如果你不想使用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-18 13:34:16

做幸福仅限于使用递归更难以获得正确的结果 - 因为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-18 18:42:28 martineau

回答

相关问题