生成升序2 ^ p*3 ^ q

Question

我有兴趣实现一个我读过的特定的Shellsort方法,它具有与bitonic排序相同的时间复杂度.然而,对于任何整数p和q,它要求间隙序列是满足表达式2 ^ p*3 ^ q的数字序列[1,N-1].在外行人的术语中,该范围内的所有数字只能被2和3整除一次.是否有相对有效的方法来生成此序列？

Answer 1

该表格的数字称为3 平滑.Dijkstra研究了生成5平滑或正则数的密切相关问题,提出了一种算法,该算法通过以1开始S然后对序列2S,3S和5S进行分类合并来生成5个平滑数的序列S. 以下是Python中对3个平滑数字的渲染,作为无限生成器.

def threesmooth():
    S = [1]
    i2 = 0  # current index in 2S
    i3 = 0  # current index in 3S
    while True:
        yield S[-1]
        n2 = 2 * S[i2]
        n3 = 3 * S[i3]
        S.append(min(n2, n3))
        i2 += n2 <= n3
        i3 += n2 >= n3

Answer 2

我能想到的最简单的就是在运行一个嵌套的循环p和q再排序结果.在Python中:

N=100
products_of_powers_of_2and3 = []
power_of_2 = 1
while power_of_2 < N:
    product_of_powers_of_2and3 = power_of_2
    while product_of_powers_of_2and3 < N:
        products_of_powers_of_2and3.append(product_of_powers_of_2and3)
        product_of_powers_of_2and3 *= 3
    power_of_2 *= 2
products_of_powers_of_2and3.sort()
print products_of_powers_of_2and3

结果

[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96]

(排序前的products_of_powers_of_2and3是

[1, 3, 9, 27, 81, 2, 6, 18, 54, 4, 12, 36, 8, 24, 72, 16, 48, 32, 96, 64]

)

鉴于products_of_powers_of_2and3log 大小为log ₂ N*log ₃ N,列表不会快速增长,并且对其进行排序似乎效率不高.例如,即使N = 100万,列表也很短,142项,所以你不必担心.