Рекурсивное создание списков индексов - Python

Question

Я пытаюсь создать списки инкрементных индексов, которые я хочу использовать для последующего анализа. Хотя следующий код работает для создания списков из 2 индексов, он не работает для произвольного числа индексов. Вот код для генерации списков из двух инкрементных индексов.

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

Например, чтобы генерировать списки из трех инкрементных индексов, мне нужно вручную изменить код на следующее:

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

Итак, в настоящее время я не могу генерировать списки инкрементных индексов для произвольного числа индексов. Я подумал, что мне может понадобиться создать рекурсивную функцию для создания списков индексов произвольной длины. Хотя я много узнал о рекурсивных функциях в Интернете, я не смог применить теорию к своему конкретному c сценарию использования. До сих пор я мог придумать только следующее (что не дает желаемого результата):

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

Кто-нибудь знает ответ на эту проблему или может указать мне правильное направление? Спасибо за ваше время, я очень ценю это.

Лучший, Кевин

РЕДАКТИРОВАТЬ: Спасибо всем за ваши ответы! Я, вероятно, должен был упомянуть, что генерация списка кортежей также хороша, и что она не обязательно должна быть рекурсивной функцией, которая делает свое дело. Я просто подумал, что это возможно только с помощью рекурсивной функции, но я не знал, что мою проблему можно решить и без рекурсивной функции.

Answer 1

itertools.combinations() решение @iz_ кажется лучшим (+1). Но если бы я написал это рекурсивно, я бы хотел сделать это повторно, без побочных эффектов:

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

Код вместо этого может быть легко изменен для генерации списков кортежей.

Answer 2

Если вы специально ищете рекурсивное решение, то вот один из подходов:

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)

---

Вывод

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