Изменить для вывода списка в рекурсии

Question

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

def getAllEndOverlappingIndices(lst, i, l):
    r = -1
    if i == len(lst):
        if l:
            print(l)
        return

    n = i + 1
    while n < len(lst) and r > lst[n][0]:
        n += 1
    getAllEndOverlappingIndices(lst, n, l)

    n = i + 1
    r = lst[i][1]
    while n < len(lst) and r > lst[n][0]:
        n += 1
    getAllEndOverlappingIndices(lst, n, l + str(lst[i]))

indices = [(0.0, 2.0), (0.0, 4.0), (2.5, 4.5), (2.0, 5.75), (2.0, 4.0), (6.0, 7.25)]
indices.sort()

print(getAllEndOverlappingIndices(indices, 0, ''))
(6.0, 7.25)
(2.5, 4.5)
(2.5, 4.5)(6.0, 7.25)
(2.0, 5.75)
(2.0, 5.75)(6.0, 7.25)
(2.0, 4.0)
(2.0, 4.0)(6.0, 7.25)
(0.0, 4.0)
(0.0, 4.0)(6.0, 7.25)
(0.0, 2.0)
(0.0, 2.0)(6.0, 7.25)
(0.0, 2.0)(2.5, 4.5)
(0.0, 2.0)(2.5, 4.5)(6.0, 7.25)
(0.0, 2.0)(2.0, 5.75)
(0.0, 2.0)(2.0, 5.75)(6.0, 7.25)
(0.0, 2.0)(2.0, 4.0)
(0.0, 2.0)(2.0, 4.0)(6.0, 7.25)

Я бы хотел, чтобы выходные данные функции представляли собой список списков, каждый из которых содержит разделенный кортежи (в настоящее время строки кортежей возвращаются). Для приведенного выше примера вместо этого будет выводиться L = [[(6.0, 7.25)], [(2.5, 4.5)], [(2.5, 4.5), (6.0, 7.25)], ..., [(0.0, 2.0), (2.0, 4.0), (6.0, 7.25)]]. Я пытался создать список в начале функции и добавлять каждый вызов функции, но я считаю, что я добавляю строки кортежей вместо самих кортежей. Можно ли изменить вывод этой функции на то, что я хотел бы, как описано? У меня нет большого опыта работы с рекурсией, и я буду признателен за любые советы.

Answer 1

В данный момент код создает гигантскую строку, потому что вы начинаете со строки и приводите каждый кортеж в строку перед тем, как объединить все вместе. Вместо этого вы можете передать пустой список и добавлять кортежи в список, пока вы не закончите sh свою комбинацию. Как только вы доберетесь до конца комбинации, добавьте ее в глобальный массив, содержащий все ваши комбинации.

# Create a global array to hold all your results.
results = []

def getAllEndOverlappingIndices(lst, i, l):
    r = -1
    if i == len(lst):
        if l:
            # Instead of printing final combination, add the combination to the global list
            results.append(l)
        return

    n = i + 1
    while n < len(lst) and r > lst[n][0]:
        n += 1
    getAllEndOverlappingIndices(lst, n, l)

    n = i + 1
    r = lst[i][1]
    while n < len(lst) and r > lst[n][0]:
        n += 1
    # Wrap the tuple in the list to take advantage of python's list concatenation
    getAllEndOverlappingIndices(lst, n, l + [lst[i]])

indices = [(0.0, 2.0), (0.0, 4.0), (2.5, 4.5), (2.0, 5.75), (2.0, 4.0), (6.0, 7.25)]
indices.sort()
# Pass in an empty list here instead of an empty string
getAllEndOverlappingIndices(indices, 0, [])

Вывод:

[[(6.0, 7.25)], [(2.5, 4.5)], [(2.5, 4.5), (6.0, 7.25)], [(2.0, 5.75)], [(2.0, 5.75), (6.0, 7.25)], [(2.0, 4.0)], [(2.0, 4.0), (6.0, 7.25)], [(0.0, 4.0)], [(0.0, 4.0), (6.0, 7.25)], [(0.0, 2.0)], [(0.0, 2.0), (6.0, 7.25)], [(0.0, 2.0), (2.5, 4.5)], [(0.0, 2.0), (2.5, 4.5), (6.0, 7.25)], [(0.0, 2.0), (2.0, 5.75)], [(0.0, 2.0), (2.0, 5.75), (6.0, 7.25)], [(0.0, 2.0), (2.0, 4.0)], [(0.0, 2.0), (2.0, 4.0), (6.0, 7.25)]]

Выходные данные отредактированы для видимости:

[[(6.0, 7.25)],
[(2.5, 4.5)],
[(2.5, 4.5), (6.0, 7.25)],
[(2.0, 5.75)],
[(2.0, 5.75), (6.0, 7.25)],
[(2.0, 4.0)],
[(2.0, 4.0), (6.0, 7.25)],
[(0.0, 4.0)],
[(0.0, 4.0), (6.0, 7.25)],
[(0.0, 2.0)],
[(0.0, 2.0), (6.0, 7.25)],
[(0.0, 2.0), (2.5, 4.5)],
[(0.0, 2.0), (2.5, 4.5), (6.0, 7.25)],
[(0.0, 2.0), (2.0, 5.75)],
[(0.0, 2.0), (2.0, 5.75), (6.0, 7.25)],
[(0.0, 2.0), (2.0, 4.0)],
[(0.0, 2.0), (2.0, 4.0), (6.0, 7.25)]]