Построение верхней треугольной матрицы рекурсивно

Question

Я ломал голову над попыткой придумать рекурсивный способ построения следующей матрицы в python. Это довольно сложная задача без указателей. Может ли кто-нибудь помочь мне?

Рекурсия следующая:

T0 = 1,
Tn+1 = [[Tn, Tn],
        [ 0, Tn]]

Я перепробовал много итераций какой-то рекурсивной функции, но не могу обернуться вокруг нее.

def T(n, arr):
    n=int(n)
    if n == 0:
        return 1
    else:
        c = 2**(n-1)
        Tn = np.zeros((c,c))
        Tn[np.triu_indices(n=c)] = self.T(n=n-1, arr=arr)
        return Tn
arr = np.zeros((8,8))
T(arr=arr, n=3)

Answer 1

Это не сложно сделать, но вы должны быть осторожны со значением нуля в рекурсии. Это не совсем точно для больших значений n:

Tn+1 = [[Tn, Tn],
        [ 0, Tn]]

Поскольку этот ноль может представлять блок нулей, например, на второй итерации, у вас есть это:

[1, 1, 1, 1],
[0, 1, 0, 1],
[ 0 , 0 , 1, 1],
[ 0 , 0 , 0, 1]

Эти четыре нуля в левом нижнем углу все представлены одним нулем в формуле. Блок нулей должен иметь ту же форму, что и блоки вокруг него.

После этого нужно заставить Нампи привести в порядок вещи для вас. numpy.block очень удобен для этого и делает его довольно простым:

import numpy as np
def makegasket(n):
    if n == 0:
        return np.array([1], dtype=int)
    else:
        node = makegasket(n-1)
        return np.block([[node, node], [np.zeros(node.shape, dtype=int), node]])


makegasket(3)

Результат:

array([[1, 1, 1, 1, 1, 1, 1, 1],
       [0, 1, 0, 1, 0, 1, 0, 1],
       [0, 0, 1, 1, 0, 0, 1, 1],
       [0, 0, 0, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 1]])

Если вы используете больший n, вам может показаться matplotlib.pyplot.imshow для отображения:

from matplotlib.pyplot import imshow

# ....

imshow(makegasket(7))

Answer 2

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

def build_matrix(n):
    size = 2**n

    # Depending on the application, even dtype=np.bool might work
    matrix = np.zeros((size, size), dtype=np.int)

    # This is t[0]
    matrix[0, -1] = 1

    for i in range(n):
        k = 2**i
        matrix[:k, -2 * k:-k] = matrix[k:2 * k, -k:] = matrix[:k, -k:]

    return matrix

Просто для забавы, вот график временных результатов для этой реализации против @ Марк Мейер . Это показывает небольшое преимущество по времени (в том числе и по памяти) использования циклического подхода в этом случае:

На моем компьютере оба алгоритма исчерпывают память при n = 15, что неудивительно.