Python: 递归

Question

虽然网上有很多关于递归的信息，但我没有找到能解决我问题的内容。我刚开始学习编程，所以如果我的问题听起来很简单，请多多包涵。

谢谢你的帮助 :)

这是我想要达到的结果：

listVariations(listOfItems, numberOfDigits) 

>>> listVariations(['a', 'b', 'c'], 1)
>>> ['a', 'b', 'c'] 

>>> listVariations(['a', 'b', 'c'], 2)
>>> ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

>>> listVariations(['a', 'b', 'c'], 3)
>>> ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

但到目前为止，我只能想到一个需要提前知道数字个数的函数。这种做法不好，也不对：

list = ['a', 'b', 'c']

def listVariations1(list):
  variations = []
  for i in list:
    variations.append(i)
  return variations

def listVariations2(list):
  variations = []
  for i in list:
    for j in list:
      variations.append(i+j)
  return variations

def listVariations3(list):
  variations = []
  for i in list:
    for j in list:
      for k in list:
        variations.append(i+j+k)
  return variations

oneDigitList = listVariations1(list)
twoDigitList = listVariations2(list)
threeDigitList = listVariations3(list)

这可能很简单，但我想不出一个好的方法来在函数自我调用时拼接字符串。

谢谢你的努力 :)

Answer 1

你可以使用 itertools.permutations 来实现这个功能。

from itertools import permutations

def listVariations(listOfItems, numberOfDigits):
    return [''.join(x) for x in permutations(listOfItems, numberOfDigits)]

如果你想用递归函数来实现类似的功能，可以这样做：

def permute(seq, n):
    for i in xrange(len(seq)):
        head, tail = seq[i:i+1], seq[0:i]+seq[i+1:]
        if n == 1: 
            yield head
        else:
            if tail:
                for sub_seq in permute(tail, n-1):
                    yield head + sub_seq
            else:
                yield head

a_list = ['a', 'b', 'c']
list(permute(''.join(a_list), 2))
a_str = 'abc'
list(permute(a_str, 2))

Answer 2

from itertools import combinations_with_replacement

这个函数正好做了你想要的事情。

Answer 3

你可以使用 product() 这个函数，它在 itertools 这个库里。