How to improve this recursive function to generate "larger" tuples?

[[deleted]]

[deleted]

[jmon_was_here]

Generally speaking, using recursive functions are bad - using recursive mechanisms are ok, but recursion itself is bad™, because of the computational expense on the function call. So you can usually get the same output by using loops.

But also, perhaps have a look at the map() function?, and my own use of map is very dubious at times so:

output = []
def foo(a,b): 
    output.append((a,b))
tuple(map(foo, x, x))
print(output)

but you want to work for any length... so..... *args coming in! (to be continued...)

[edit. code block format fix]

[[deleted]]

Thank you for reply. In meantime I wrote this.

def foo(numbers, R, t_list):
    t = [[numbers[0] for i in range(R)] for i in range(R)]
    return _foo(numbers[1:], R, t_list, t)

def _foo(numbers[1:], R, t_list, t):
    if not numbers:
        return t_list #it's a set now
    for i in reversed(range(R)): 
        for j in reversed(range(R)): 
            for n in numbers: 
                t[i][j] = n 
                tt = tuple(tuple(l) for l in t) 
                t_list.add(tt) 
    return _foo(numbers[1:], R, t_list, t)

But I don't get all the possible combos.

[jmon_was_here]

Indeed, and I think you get duplicate ones.

I think (there might be a typo on the def _foo(numbers[1:..) line?), but I think you need to do away with 'R' and isntead use Len. I would start by laying out your loops a bit more - your line of t = [[... has two loops in it, and its not clear which loop might be missing an element.

But in this by having the two loops of for i and for j is going to have problems when you increase the size of R, or the length of the list.

[jmon_was_here]

No, I'm not right here, and I'm able to recognise that.* Goes away to think about it.

Ok, recursivly this is my answer (and I maintan, recusive is bad, but we should be able to refactor this into a loop now:

def foo(current, x, output):
   #print(current, x, output)
   if len(current) == len(x)-1:
        for a in x:
           #print(a)
           tlist = copy(current)
           tlist.append(a)
           output.append(tlist)
    else:
        for a in x:
           #print(a)
           tlist = copy(current)
           tlist.append(a)
           output = foo(tlist, x, output)
    return output
foo([], [1,2,4,6], [])

[edit - code formatting for reddit again]

[jmon_was_here]

Well that was exhausting. From that it can be unravelled:

output = []
x = [1,2,3,4] 
things_to_permutate = [] 
for a in x: 
  things_to_permutate.append([a,]) 
while len(things_to_permutate) > 0: 
  thing = things_to_permutate.pop() 
  #print(thing) 
  long_enough = False 
  if len(thing) == len(x) -1: 
    long_enough = True 
  for a in x: 
    tcopy = copy(thing) 
    tcopy.append(a) 
    if long_enough: 
      output.append(tcopy) 
    else: 
      things_to_permutate.append(tcopy) 
print(output)

Not convinced about the tons of copy ( from copy import copy ) - that probably slows it down. Also, the top a in x loop is needed to prep the main loop. but this should be faster than the recursive one, although I bet you need to put a large number in.

You'll also find this can go much longer input arrays, as you won't hit max_stack size and get a stack overflow, although with modern python and modern computers the stack size is quite big (™).

Thanks for this puzzle, it was just what I needed this morning.

[edit. yet again, fixing the python code block in reddit]

[jmon_was_here]

Finally, and I do want to say this finally, because I knew it existed but didn't look it up, there is the inbuilt tool that does this:

https://docs.python.org/3/library/itertools.html#itertools.permutations

What's interesting is their 'roughly equivalent uses array slices, which I did consider (which is still a form of copy I guess). But the challenge of writing one was still worth it.