Разделение сегмента блока на две части рекурсивно

Я хотел бы создать простой мультифрактальный (Биномиальная Мера). Это можно сделать следующим образом:

Биномиальная мера является вероятностной мерой, которая удобно определяется рекурсивной конструкцией. Начните с расщепления $ I: = [0, 1] $ на два подинтервала $ I_0 $ и $ I_1 $ равной длины и присвойте им массы $ m_0 $ и $ m_1 = 1 – m_0 $. С двумя подинтервалами происходит одно и то же и так далее: на втором этапе, например, четыре подпоследовательности $ I_ {00}, I_ {01}, I_ {10}, I_ {11} $ имеют массы $ m_0m_0, m_0m_1 m_1m_0 m_1m_1 $ соответственно.

Рудольф Х. Риди. Введение в мультифракталы

И это должно выглядеть так на 13-й итерации: Рисунок 1

Я попытался реализовать его рекурсивно, но что-то пошло не так: он использует ранее измененный интервал как для левого, так и для правого

def binom_measuare(iterations, val_dct=None, interval=[0, 1], p=0.4, temp=None): if val_dct is None: val_dct = {str(0.0): 0} if temp is None: temp = 0 temp += 1 x0 = interval[0] + (interval[1] - interval[0]) / 2 x1 = interval[1] print(x0, x1) m0 = interval[1] * p m1 = interval[1] * (1 - p) val_dct[str(x0)] = m0 val_dct[str(x1)] = m1 print('DEBUG: iter before while', iterations) while iterations != 0: if temp % 2 == 0: iterations -= 1 print('DEBUG: iter after while (left)', iterations) # left interval = [interval[0] + (interval[1] - interval[0]) / 2, interval[1] / 2] binom_measuare(iterations, val_dct, interval, p=0.4, temp=temp) elif temp % 2 == 1: print('DEBUG: iter after while (right)', iterations) # right interval = [interval[0] + (interval[1] - interval[0]) / 2, interval[1]] binom_measuare(iterations, val_dct, interval, p=0.4, temp=temp) else: return val_dct 

Кроме того, я попытался сделать это, используя for-loop, и он выполняет хорошую работу до второй итерации: на третьей итерации он использует множители 2 ^ 3, а не 3 $ m_0m_0m_0 $ и 2 ^ 4 на четвертом, а не 4 и так далее:

 iterations = 4 interval = [0, 1] val_dct = {str(0.0): 0} p = 0.4 for i in range(1, iterations): splits = 2 ** i step = interval[1] / splits print(splits) for k in range(1, splits + 1): deg0 = splits // 2 - k // 2 deg1 = k // 2 print(deg0, deg1) val_dct[str(k * step)] = p ** deg0 * (1 - p) ** deg1 print(val_dct) 

Концепция кажется очень простой в реализации, и, вероятно, кто-то ее уже сделал. Я просто смотрю из-под другого угла?


UPD: Пожалуйста, убедитесь, что ваше предложение может достичь результатов, которые показаны на рисунке выше ( p=0.4, iteration=13 ).

UPUPD: Билл Белл дал хорошую идею для достижения того, что упоминал Риди в статье. Я использовал подход Билла и написал функцию, которая реализует ее для необходимого количества итераций и $ m_0 $ (см. Мой ответ ниже ).

3 Solutions collect form web for “Разделение сегмента блока на две части рекурсивно”

Если я правильно понял принцип, вы могли бы использовать библиотеку символической алгебры sympy для выполнения этого расчета в этих строках.

 >>> from sympy import * >>> var('m0 m1') (m0, m1) >>> layer1 = [m0, m1] >>> layer2 = [m0*m0, m0*m1, m0*m1, m1*m1] >>> layer3 = [] >>> for item in layer2: ... layer3.append(m0*item) ... layer3.append(m1*item) ... >>> layer3 [m0**3, m0**2*m1, m0**2*m1, m0*m1**2, m0**2*m1, m0*m1**2, m0*m1**2, m1**3] 

Интервалы всегда равны.

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

 >>> [_.subs(m0,0.3).subs(m1,0.7) for _ in layer2] [0.0900000000000000, 0.210000000000000, 0.210000000000000, 0.490000000000000] 

Я думаю, что проблема в вашем цикле while: он неправильно обрабатывает базовый случай вашей рекурсии. Он останавливается только тогда, когда итерации равны 0, но в противном случае продолжается цикличность. Если вы хотите отладить, почему это образует бесконечный цикл, я оставлю его вам. Вместо этого я сделал все возможное, чтобы исправить эту проблему.

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

 def binom_measuare(iterations, val_dct=None, span=[0, 1], p=0.4, temp=None): interval = span[:] ... ... print('DEBUG: iter before while', iterations) if iterations > 0: if temp % 2 == 0: print('DEBUG: iter after while (left)', iterations) # left interval = [interval[0] + (interval[1] - interval[0]) / 2, interval[1] / 2] binom_measuare(iterations-1, val_dct, interval, 0.4, temp) else: print('DEBUG: iter after while (right)', iterations) # right interval = [interval[0] + (interval[1] - interval[0]) / 2, interval[1]] binom_measuare(iterations-1, val_dct, interval, 0.4, temp) else: return val_dct 

Это заканчивается и, кажется, дает несколько разумные результаты. Тем не менее, я задаюсь вопросом о ваших вычислениях интервалов, когда правая граница часто может быть меньше, чем левая. Рассмотрим [0.5, 1.0] … рекурсия слева-ребенка будет на интервале [0.75, 0.5]; это то, что вы хотели?

Это моя адаптация ответа @Bill Bell на мой вопрос. Он обобщает идею, которую он предоставил.

 import matplotlib.pyplot as plt from sympy import var def binom_measuare(iterations, p=0.4, current_layer=None): var('m0 m1') if current_layer is None: current_layer = [1] next_layer = [] for item in current_layer: next_layer.append(m0*item) next_layer.append(m1*item) if iterations != 0: return binom_measuare(iterations - 1, current_layer=next_layer) else: return [i.subs(m0, p).subs(m1, 1 - p) for i in next_layer] 

Давайте построим вывод

 y = binom_measuare(iterations=12) x = [(i+1) / len(y) for i in range(len(y))] x = [0] + x y = [0] + y plt.plot(x, y) 

введите описание изображения здесь

Думаю, у нас это есть.

  • Как найти количество вложенных списков в списке?
  • Цикл возврата функции Python
  • разделите список, используя рекурсию
  • Как я могу вернуть нечетные числа списка, используя только рекурсию в Python?
  • Рекурсивный поиск файлов Python и переход в один каталог назначения
  • Рекурсивно уменьшать список на 1
  • Викторина по рекурсии - не удалось решить
  • Почему рекурсия в python настолько медленная?
  • Преобразование python decimal в строку в глубоко вложенном и непредсказуемом списке
  • Возврат рекурсии python Нет типа
  • рекурсивный dircmp (сравните два каталога, чтобы они имели одинаковые файлы и подкаталоги)
  •  
    Interesting Posts for Van-Lav
    Python - лучший язык программирования в мире.