Печатайте комбинации n-длины из списка символов, используя рекурсию

Question

Я должен решить это упражнение, используя рекурсию.

Реализовать функцию в Python, которая получает список параметров символов и целое число n.Функция должна печатать все возможные комбинации длины n, где каждый символ может быть показан более одного раза.

Это очень ошеломляет меня, все это мышление рекурсивно в целом.

Например, для этой проблемы я думаю уже полтора часа, не зная, о чем я думаю.Я не знаю, как начать мыслить рекурсивно, с чего я начинаю?

Я написал какую-то ерунду:

def print_sequences(char_list, n):
if len(char_list) == 1:
    print(char_list[1])
else:
    sub_str = ""
    for c in char_list:
        print_sequences(list(sub_str + c), n)

Пожалуйста, помогите мне развить чувство рекурсии.

Answer 1

Вы совсем близко.Вместо len(char_list) == 1 необходимо проверить, что длина вашего накопленного списка «пулов» равна параметру n.Однако, чтобы создать список для накопления комбинаций, создайте один дополнительный параметр в сигнатуре функции:

def print_sequences(char_list, n, _accum):
  if len(_accum) == n:
     print(_accum)
  else:
     for c in char_list:
        print_sequences(char_list, n, _accum+[c])


print_sequences([1, 2, 3, 4], 4, [])

Вывод:

[1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 1, 4]
[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 1, 2, 4]
[1, 1, 3, 1]
[1, 1, 3, 2]
[1, 1, 3, 3]
[1, 1, 3, 4]
[1, 1, 4, 1]
[1, 1, 4, 2]
[1, 1, 4, 3]
[1, 1, 4, 4]
[1, 2, 1, 1]
....

Редактировать: реализация _accum каксписок по умолчанию:

def print_sequences(char_list, n, _accum=[]):
  if len(_accum) == n:
    print(_accum)
  else:
    for c in char_list:
      print_sequences(char_list, n, _accum+[c])

print_sequences([1, 2, 3, 4], 4)