递归地将单元段分成两部分 [英] Splitting the unit segment into two parts recursively

问题描述

我想创建一个简单的多重分形(二项式测度).可以按如下方式进行:

<块引用>

二项式测度是一种概率测度，可以通过递归构造方便地定义.首先将 $ 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 $.

我试图递归地实现它，但出了点问题:它在左孩子和右孩子中都使用了先前更改的间隔

def binom_measuare(iterations, val_dct=None, interval=[0, 1], p=0.4, temp=None):如果 val_dct 为 None:val_dct = {str(0.0): 0}如果温度为无:温度 = 0温度 += 1x0 = 间隔[0] + (间隔[1] - 间隔[0])/2x1 = 间隔[1]打印(x0，x1)m0 = 间隔[1] * pm1 = 间隔[1] * (1 - p)val_dct[str(x0)] = m0val_dct[str(x1)] = m1print('DEBUG: iter before while', 迭代次数)而迭代 != 0:如果温度 % 2 == 0:迭代 -= 1print('DEBUG: iter after while (left)', 迭代)# 剩下间隔 = [间隔[0] + (间隔[1] - 间隔[0])/2, 间隔[1]/2]binom_measuare(迭代，val_dct，间隔，p=0.4，temp=temp)elif 温度 % 2 == 1:print('DEBUG: iter after while (right)', 迭代)# 正确的间隔 = [间隔[0] + (间隔[1] - 间隔[0])/2, 间隔[1]]binom_measuare(迭代，val_dct，间隔，p=0.4，temp=temp)别的:返回 val_dct

此外，我尝试使用 for 循环来做到这一点，并且它在第二次迭代之前做得很好:在第三次迭代中它使用 2^3 乘数而不是 3 $ m_0m_0m_0 $ 和 2^4 在第四次迭代而不是 4 等:

迭代次数 = 4间隔 = [0, 1]val_dct = {str(0.0): 0}p = 0.4对于范围内的 i(1，迭代):分裂 = 2 ** i步 = 间隔 [1]/拆分打印(拆分)对于范围内的 k(1，拆分 + 1):deg0 = 分裂//2 - k//2deg1 = k//2打印(deg0，deg1)val_dct[str(k * step)] = p ** deg0 * (1 - p) ** deg1打印(val_dct)

这个概念似乎很容易实现，可能有人已经做到了.我只是从另一个角度看吗?

<小时>

UPD:请确保您的建议能够达到上图所示的结果(p=0.4，迭代=13).

UPUPD:Bill Bell 提供了一个很好的想法来实现 Riedi 在文章中提到的内容.我使用了 Bill 的方法并编写了一个函数来实现它所需的迭代次数和 $m_0$(请参阅我的下面的答案).

解决方案

如果我正确理解了原理，你可以使用 sympy 符号代数库来进行这个计算，沿着这些路线.

<预><代码>>>>从 sympy 导入 *>>>var('m0 m1')(m0, m1)>>>layer1 = [m0, m1]>>>layer2 = [m0*m0, m0*m1, m0*m1, m1*m1]>>>layer3 = []>>>对于 layer2 中的项目:... layer3.append(m0*item)... layer3.append(m1*item)...>>>第3层[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]

I would like to create a simple multifractal (Binomial Measure). It can be done as follows:

The binomial measure is a probability measure which is defined conveniently via a recursive construction. Start by splitting $ I := [0, 1] $ into two subintervals $ I_0 $ and $ I_1 $ of equal length and assign the masses $ m_0 $ and $ m_1 = 1 - m_0 $ to them. With the two subintervals one proceeds in the same manner and so forth: at stage two, e.g. the four subintervals $ I_{00}, I_{01}, I_{10}, I_{11} $ have masses $ m_0m_0, m_0m_1 m_1m_0 m_1m_1 $ respectively.

Rudolf H. Riedi. Introduction to Multifractals

And it should look like this on the 13 iteration:

I tried to implement it recursively but something went wrong: it uses the previously changed interval in both left child and the right one

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

Also, I have tried to do this using for-loop and it is doing good job up to the second iteration: on the third iteration it uses 2^3 multipliers rather than 3 $ m_0m_0m_0 $ and 2^4 on the fourth rather than 4 and so on:

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)

The concept seems very easy to implement and probably someone has already done it. Am I just looking from another angle?

---

UPD: Please, may sure that your suggestion can achieve the results that are illustrated in the Figure above (p=0.4, iteration=13).

UPUPD: Bill Bell provided a nice idea to achieve what Riedi mentioned in the article. I used Bill's approach and wrote a function that implements it for needed number of iterations and $m_0$ (please see my answer below).

解决方案

If I understand the principle correctly you could use the sympy symbolic algebra library for making this calculation, along these lines.

>>> 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]

The intervals are always of equal size.

When you need to evaluate the distribution you can use the following kind of code.

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

这篇关于递归地将单元段分成两部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！