Распечатать все смежные подмассивы

Question

Я хочу написать рекурсивную функцию для добавления всех смежных подмассивов в список. Функция работает, но есть некоторое дублирование. Я хотел знать, есть ли способ избежать этого.

def numSubArray(array, result):
    if len(array) == 0:
        return []
    result.append(array)
    numSubArray(array[1:], result)
    numSubArray(array[:-1], result)
    return result

Answer 1

У вас есть массив в качестве входных данных, и вы хотите вернуть список со всеми значениями в этом массиве, предпочтительно используя рекурсивную функцию?

Я думаю, вы хотите это:

new_list = []
def array_to_list(arr): 
     for i in arr: 
         if isinstance(i,list) or isinstance(i,array.array): 
             array_to_list(arr) 
         else: 
             new_list.append(i)
a = arr.array('d',  [1.1, 3.5, 4.5])
array_to_list(a)
print(new_list)

Последняя строка напечатает ваш массив!

Answer 2

решение 1. Грубая рекурсия и удаление дубликатов

Вы можете устранить дублирование, используя set.
Но вы не можете сделать set из list с, так как list не является хэш .
А для эффективности вы можете сначала собрать индексные пары, а затем нарезать:

def num_sub_array(array):
    return [
        array[i:j] for i, j in build_pair_set(0, len(array))
    ]


def build_pair_set(start: int, end: int) -> set:
    return set() if start == end else (
        {(start, end)}
        | build_pair_set(start + 1, end)
        | build_pair_set(start, end - 1)
    )


print(sorted(num_sub_array([1, 2, 3, 4])))

output:

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

---

решение 2. рекурсия без избыточности

def num_sub_array(array):
    if not array:
        return []
    return [array[i:] for i in range(len(array))] + num_sub_array(array[:-1])


print(sorted(num_sub_array([1, 2, 3, 4])))

вывод:

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

---

На самом деле, решение 2 * num_sub_array имеет хвостовую рекурсию. Таким образом, вы можете изменить его на l oop.

Решение 3. L oop

def num_sub_array(array):
    return [
        array[i:j]
        for i in range(len(array))
        for j in range(i + 1, len(array) + 1)
    ]


print(sorted(num_sub_array([1, 2, 3, 4])))

вывод:

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

---

Я использовал sorted для сравнения двух методов. Это не обязательно.

Answer 3

Ваш код, по-видимому, производит следующее для получения всех подпоследовательностей непустого array:

1. array (то есть все подпоследовательности, которые включают оба первый и последний элементы в array)
2. все подпоследовательности array[1:] (то есть все подпоследовательности, которые не включают первый элемент в array
3. все подпоследовательности array[:-1] (то есть все подпоследовательности, которые не включают последний элемент в array

Таким образом, источник дублирования ясен: любая подпоследовательность который не имеет ни первого, ни последнего элемента в array, будет учитываться дважды (при любом вызове, то есть чем длиннее array, тем больше копий вы можете получить).

Решение, надеюсь, также ясно, удалить # 1 (это будет охватываться следующим), и либо

• замену # 3 будут все подпоследовательности, которые do включают первый элемент в array, или
• замените # 2 всеми подпоследовательностями, которые do включают последние элемент в array