CODEWITHSUNDEEP
pythonlistrecursionindices
Kevin Südmersen
Kevin Südmersen

Reputation: 971

Recursively generating lists of indices - Python

I am trying to generate lists of incrementing indices which I want to use for later analysis. While the following code is working for generating lists of 2 indices, it is not working for an arbitrary number of indices. Here is the code for generating lists of 2 incrementing indices.

max_len = 9
idxs_len2 = [[idx1, idx2] for idx1 in range(1, max_len) for idx2 in range(idx1 + 1, max_len)]

For example, to generate lists of three incrementing indices, I would manually need to change the code to the following:

idxs_len3 = [
    [idx1, idx2, idx3] 
    for idx1 in range(1, max_len) 
    for idx2 in range(idx1 + 1, max_len) 
    for idx3 in range(idx2 + 1, max_len)
]

So, at the moment, I am not able to generate lists of incrementing indices for an arbitrary number of indices. I thought I might need to create a recursive function to create lists of indices with an arbitrary length. Although I found a lot about recursive functions online, I wasn't able to apply the theory to my specific use case. All I could come up with so far was the following (which is not yielding the desired output):

def generate_idxs(idx1, all_idxs, max_depth=3, max_len=9):
    current_idxs = []
    for idx2 in range(idx1 + 1, max_len):
        if len(current_idxs) < max_depth:
            current_idxs.append(idx2)
        else:
            all_idxs.append(current_idxs)
            generate_idxs(idx2, all_idxs, max_len=9)

# Calling the function
idxs_len3_test = []
generate_idxs(0, idxs_len3_test, max_len=9)
idxs_len3 == idxs_len3_test # ==> Yields False

Does anyone know the answer to this problem, or can point me to the right direction? Thanks for your time, I highly appreciate it.

Best, Kevin

EDIT: Thank you all for your answers! I should probably have mentioned, that generating a list of tuples is also fine and that it didn't necessarily need to be a recursive function that does the trick. I just thought that it would only be possible with a recursive function, but I wasn't aware that my problem could also be solved without a recursive function.

Upvotes: 0

Views: 66

Answers (2)

cdlane
cdlane

Reputation: 41905

The itertools.combinations() solution of @iz_ seems best (+1). But if I were to write this recursively, I would want to do it re-entrantly, sans side effects:

def generate_idxs(max_depth, max_index, start=1):
    if start < max_index:

        if max_depth == 1:
            return [[index] for index in range(start, max_index)]

        return [[start, *index] for index in generate_idxs(max_depth - 1, max_index, start + 1)] + generate_idxs(max_depth, max_index, start + 1)

    return []

print(generate_idxs(4, 6))

OUTPUT

> python3 test.py
[[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]
>

The code can be easily modified to generate lists of tuples instead.

Upvotes: 1

Ajay Dabas
Ajay Dabas

Reputation: 1444

If you're specifically looking for a recursive solution, then here's one approach to do it.

def generate_idxs(start, all_idxs, current_idxs, max_depth, max_len):
    if len(current_idxs) == max_depth:
        all_idxs.append(current_idxs.copy()) # Add the solution and return
        return
    for i in range(start + 1, max_len):
        current_idxs.append(i) # Add an element to the end
        generate_idxs(i, all_idxs, current_idxs, max_depth, max_len) # Recurse
        current_idxs.pop() # Remove the element at end (Backtrack)
    return

all_idxs = []
generate_idxs(0, all_idxs, [], 4, 6)
print(all_idxs)

Output

[[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]

Upvotes: 1

Related Questions