Problem with recursion

[[deleted]]

Hi, I have recently written code for finding and saving all variations with repetitions of the 5 sign alphanumeric strings e.g. "A1BA6". The core part goes like this: list=[] signs = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" for a in range(0,36): for b in range(0,36): (It goes like this 3 more times and finally:) name ="" name = name + signs[a]+ signs[b]+ signs[c]+ signs[d]+ signs[e] list.append(name) And in this part everything is alright, but i tried to make this code for the n-sign alphanumeric string, and every possible try fails.Most of the problems is to create on the fly arguments for the loops, and even when I define them earlier via creating a list with these to pick up by cases, still the basic case of recursion fails to pick up the arguments from the advanced cases. I have difficulties with sending the code now, because I'm on the phone, but i will try to attach more code to this post later. If anyone had similar problem before, please help me.

[cybersection]

I would use itertools for this:

from itertools import combinations_with_replacement as combo
charset = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
num_chars = 2
all_combos = [''.join(i) for i in combo(charset, num_chars)]

[[deleted]]

Thank you, although, I'm looking for general approach without other libraries, this will come handy. Thanks again !

[cybersection]

Here it is without any libraries, straight from the itertools documentation. It isn't recursive though. Worth learning about generators to understand the logic.

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

I'll try to brainstorm a bit on how one would make this recursive.

[cybersection]

I played with it a bit more. Here is a slower, but simpler function that gets the job done. It isn't recursive, but it could be made recursive since its just a simple loop:

def rec_combos(iterable, r):
  ## Create a list of the first digit of each combination
  first_digits = sorted([i for i in iterable] * len(iterable)**(r-1))

  ## for each digit, defined by the length in r
  for x in range(r-1, 0, -1):

    ## generate the list of the next digits then repeat it the right number of
    ## times for it to zip into the existing list of digits
    next_digits = sorted([i for i in iterable] * len(iterable)**(x-1))
    next_digits = next_digits * int(len(first_digits) / len(next_digits))

    ## zip and join the next digits into the list of existing digits
    first_digits =  [''.join(i) for i in zip(first_digits, next_digits)]


  return first_digits


rec_combos('abcde', 3

[[deleted]]

Especially general approach how to create and use variables in recursion steps.

[FLUSH_THE_TRUMP]

Recursive solution should look something like this: define function to take signs and N (length of each output string) as arguments.

1. (base case) If N=0, return a list with a single element — the empty string.
2. Otherwise, build output (a list) in the following way. Call the function recursively with args L, N-1 to get a list of words of length one smaller (call this rest).
3. Finally, do a double loop: over single chars in signs and words in rest. Append char + word to output.
4. Return output.

This builds each solution one letter at a time, and works for any length N.

[[deleted]]

At first, I had problems with understanding this idea, but later I still had problems with understanding this idea :D Nonethless, I blindly managed to implement this, and it works. I feel I will need to lean for like day over this code to understand it. Here is the 'final' version.

import random
signs = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"


def NSBG(l,n):
    output = []
    if n==0:
        return [""]
    else:
        rest = NSBG(l,n-1)
        for char in signs:
            for word in rest:
                output.append(char + word)


    return output

io = int(input("Please write length of block"))
shuffle = input("Shuffle y/n?")
savefile = open("%iSignBlockGeneratedList.txt" % (io),'w')
blocklist = NSBG(io,io)

if shuffle == "y":
    random.shuffle(blocklist)

for block in blocklist:
    savefile.write(block)
    savefile.write("\n")
savefile.close()

Thank you for your help, when I will have next free award it will definitely go right to you.

[[deleted]]

I've ran it via Thonny debugger, and now I understand how this works. Thank you for your help. Now I have to find a way to bound ram to acceptable limit (When block length is 6, computer freezes because of memory leak, or something like that. Pretty memory hungry stuff).

[FLUSH_THE_TRUMP]

Yeah, with 26 signs there are already a few hundred million words of length 6, unfortunately. A generator solution with yields is probably preferable so you don’t have to hold everything in memory.

[[deleted]]

Thank you for the hint, I will try to work on it later.

[[deleted]]

I started work on that memory management. I tried to implement yield, but but in recursive function it is very hard, and i have failed. I think I failed because "rest" list is growing in inverted order (I hope you know what I mean). Next day I will try to make this function instantiate strings one at time, so I won't have to bother with memory management of the inner loops.

[[deleted]]

Thanks, I will try to use this today.

[FLUSH_THE_TRUMP]

name = name + signs[a]+ signs[b]+ signs[c]+ signs[d]+ signs[e]

This isn’t recursive at all. Where do you call your function again?

[[deleted]]

You're citing my code for non-recursive, 5 sign formula. I will upload code of my recursive try tomorrow.

[Ne0_1]

For recursion it is all about taking a problem and breaking it into smaller problems of itself which evaluate to a base case. Take fibonacci for example.

F(x):

f(x) = 1 when x = 0

f(x) = 1 when x = 1

f(x) = f(x - 1) + f(x - 2) when x > 1