Разделение сегмента блока на две части рекурсивно
Я хотел бы создать простой мультифрактальный (Биномиальная Мера). Это можно сделать следующим образом:
Биномиальная мера является вероятностной мерой, которая удобно определяется рекурсивной конструкцией. Начните с расщепления $ 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-й итерации: 
Я попытался реализовать его рекурсивно, но что-то пошло не так: он использует ранее измененный интервал как для левого, так и для правого
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 $ (см. Мой ответ ниже ).
- Как вернуть значение из рекурсивной функции в python?
- Комбинации замков для динамического размера замка
- Сглаживание списка рекурсивно
- Как определить рекурсивную функцию для объединения двух отсортированных списков и возврата нового списка с возрастающим порядком в Python?
- рекурсивная функция python, которая печатает от 0 до n?
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 либо в cygwin, либо в Linux, который не является debian?