python - Python 再帰

Question

電話の数字列を表す文字の可能な組み合わせをすべて生成する必要があります...たとえば、エントリが「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]]

score 10 · Accepted Answer

あなたが探していると思います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では）。

score 4 · Accepted Answer

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

score 0 · Accepted Answer

再帰のみを使用するように制限することは、私が予想したよりも正しく行うのが難しいことでした。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']

python - Python 再帰

3 に答える 3

Related

Reference