生成升序顺序2 ^ P * 3 ^ Q [英] Generating Ascending Sequence 2^p*3^q

问题描述

我感兴趣的是实现特定希尔方法，我读到了有同样的时间复杂度为双调排序。但是，它需要的间隙序列是数字的序列[1，N-1]中满足离pression 2 ^ P * 3 ^ Q为任何整数p和q。通俗地说，在该范围内所有的数字是只有整除2和3倍的整数金额。是否有一个相对高效生成此序列的方法？

I was interested in implementing a specific Shellsort method I read about that had the same time complexity as a bitonic sort. However, it requires the gap sequence to be the sequence of numbers [1, N-1] that satisfy the expression 2^p*3^q for any integers p and q. In layman's terms, all the numbers in that range that are only divisible by 2 and 3 an integer amount of times. Is there a relatively efficient method for generating this sequence?

推荐答案

该形式的数字被称为3 顺利 。 Dijkstra算法的研究产生5-光滑或常规的数字，提出了一种算法，生成5-序列S的密切相关的问题顺利通过数字开始，1个S，然后做序列2S，3S和5S的排序合并。下面是这个想法在Python 3光滑号的渲染，一个无限的发电机。

Numbers of that form are called 3-smooth. Dijkstra studied the closely related problem of generating 5-smooth or regular numbers, proposing an algorithm that generates the sequence S of 5-smooth numbers by starting S with 1 and then doing a sorted merge of the sequences 2S, 3S, and 5S. Here's a rendering of this idea in Python for 3-smooth numbers, as an infinite generator.

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

这篇关于生成升序顺序2 ^ P * 3 ^ Q的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！