碎形數列

fractal_sequence.py

'''碎形數列之一…每隔 n 個空格填入數字1、2、3、4、5 ....，例如 n 為 2 時…

1 _ _ 2 _ _ 3 _ _ 4 _ _ 5 _ _ 6 _ _ 7 _ _ 8 _ _ 9 _ _ ....

接著，在上面的數列中，每隔  2 個空格填入數字1、2、3、4、5 ....

1 1 _ 2 _ 2 3 _ _ 4 3 _ 5 _ 4 6 _ _ 7 5 _ 8 _ 6 9 _ _ ....

繼續在上面的數列中，每隔  2 個空格填入數字1、2、3、4、5 ....

1 1 1 2 _ 2 3 _ 2 4 3 _ 5 _ 4 6 3 _ 7 5 _ 8 4 6 9 _ _ ....

就這麼一直重複…

1 1 1 2 1 2 3 _ 2 4 3 _ 5 2 4 6 3 _ 7 5 _ 8 4 6 9 3 _ ....

1 1 1 2 1 2 3 1 2 4 3 _ 5 2 4 6 3 _ 7 5 2 8 4 6 9 3 _ ....

1 1 1 2 1 2 3 1 2 4 3 1 5 2 4 6 3 _ 7 5 2 8 4 6 9 3 _ ....

1 1 1 2 1 2 3 1 2 4 3 1 5 2 4 6 3 1 7 5 2 8 4 6 9 3 _ ....

1 1 1 2 1 2 3 1 2 4 3 1 5 2 4 6 3 1 7 5 2 8 4 6 9 3 1 ....

得到的數列，從左而右遇到第一個 1、2、3、4 …分別刪掉，得到的數列還是跟原來的一樣。

'''

def none_indices_with_gap(seq, gap):
    # 找出可放數字的空盒
    none_indices = [i for i in range(len(seq)) if seq[i] is None]
    # 每個數字之間要有 gap 個空盒
    return none_indices[0::gap + 1]  

def fill_fractal_sequence(seq, gap):
    indices = none_indices_with_gap(seq, gap)
    
    if len(indices) == 0: # 已經沒有可填的空盒了
        return seq
    else:
        # 每隔 gap 空盒填入數字 1、2、3、4...
        for i in range(len(indices)):
            seq[indices[i]] = i + 1            
        return fill_fractal_sequence(seq, gap)
    
def fractal_sequence(leng, gap):
    seq = [None] * leng # None 表示空盒
    return fill_fractal_sequence(seq, gap)
    
leng = 100
gap = 2
print(fractal_sequence(leng, gap))

# 另一個解法
def fractal_sequence2(seq, n, i, limit):
    if len(seq) < limit:
        seq.append(n)
        seq.append(seq[i])
        seq.append(seq[i + 1])
        return fractal_sequence2(seq, n + 1, i + 2, limit)
    return seq[0:limit]

print(fractal_sequence2([], 1, 0, leng))