2

I have to solve this exercise using recursion.

Implement a function in Python which recieves as parameters list of characters and an integer n. The function has to print all the possible combinations in the length of n, where every character can be shown more than one time.

It's very mind-blowing for me, all this thinking recursively generally.

For example, for this problem, I think already one and a half hour, not knowing what I'm thinking about. I don't know how to start thinking recursively, what am I starting from?

I have written some nonsense:

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)

Please help me develop some sense of recursion.

Jongware
  • 22,200
  • 8
  • 54
  • 100
HelpMe
  • 91
  • 10

1 Answers1

2

You are quite close. Instead of len(char_list) == 1, you need to check that the length of your accumulated "pool" list is equal to the parameter n. However, to create a list to accumulate the combinations, create one additional parameter in the signature of the function:

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, [])

Output:

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

Edit: implementing _accum as a default list:

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)
Ajax1234
  • 69,937
  • 8
  • 61
  • 102
  • If your function needs _accum to be given an empty list, why not just set it to optional and make it default to that value? `def print_sequences(char_list, n, _accum=[]):` – Adam Dadvar Nov 30 '18 at 16:53
  • @AdamDadvar That is a possibility, however, default arguments can product [unexpected behavior](https://stackoverflow.com/questions/8951033/python-default-arguments-and-argument-names) on subsequent function calls. Generally, the best way to handle default arguments is to actually set the parameter equal to `None`, and then reassign the value to the truly desired default value later in the function. However, I think that process is overkill in the context of this question. – Ajax1234 Nov 30 '18 at 19:42
  • We must not recieve any parameter except for the char_list and n. What can I do? – HelpMe Dec 01 '18 at 11:06
  • The function must have signature of maximum 2 arguments: 'char_list' and 'n' only. Can you explain me please how can I accustom myself to think recursively? – HelpMe Dec 01 '18 at 19:24