我必须在Python中编写一个shell排序程序，但一方面我必须有一个程序使用一些特殊的间隙序列创建文本文件，这是我的shell排序会得到它的差距数字。如何实现Pratt间隙序列？（Python，Shell Sort）

On Wikipedia（http://en.wikipedia.org/wiki/Shellsort）Pratt序列的等式如下：“连续数字形式2^p * 3^q”，它产生1,2,3,4,6,8,9,12 ，...

我没有得到的是如何实现这个，基本上P和Q是什么？

最坏情况下的时间复杂度为O（n日志^ 2N）

我对序列发生器文件目前代码：

def Hibbard(big): 
     H = open("Hibbard.txt","w") 
     i = 1 
     math = (2**i)-1 
     while math <= big: 
      H.write(str(math)) 
      H.write("\n") 
      i+=1 
      math = (2**i)-1 
    def Pratt(big): 
     pass 
    def SedA(big): 
     SA = open("SedgewickA.txt","w") 
     SA.write("1\n") 
     i = 1 
     math = (4**i)+3*2**(i-1)+1 
     while math <= big: 
      SA.write(str(math)) 
      SA.write("\n") 
      i+=1 
      math = (4**i)+3*2**(i-1)+1 
    def SedB(big): 
     pass 
    def main(): 
     big = int(input("Enter the largest gap: ")) 
     Hibbard(big)

普拉特（大）

 SedA(big)

SEDB（大）

main()

来源

2014-09-21 Andrew Nelson

我还没有尝试过编码，因为我根本不知道从哪里开始。这真的是一个数学问题。如果有帮助，我已经编码了4个我需要的其他4个，我会把它放在这里。 – 2014-09-21 22:53:03

我n Pratt序列的定义，p和q分别是2和3分别提出的指数。你需要找到所有2和3的幂的乘积不能大于你的排序的最大间隙大小。要做到这一点，制作一张桌面，其顶部为2，幂为3，并填充每个单元格，直到它们超过最大间隙大小。例如，在最大间隙大小为500的情况下，表格如下所示：

1 2 4 8 16 32 64 128 256 
    3 6 12 24 48 96 192 384 
    9 18 36 72 144 288 
    27 54 108 216 432 
    81 162 324 
243 486

现在模拟Python中该表的生成。

def generate_pratt(max_size): 
    """Generate a sorted list of products of powers of 2 and 3 below max_size""" 
    # for https://stackoverflow.com/q/25964453/2738262 
    products = [] 
    pow3 = 1 # start with q = 0 
    while pow3 <= max_size: 
     # At this point, pow3 = 3**q, so set p = 0 
     pow2 = pow3 
     while pow2 <= max_size: 
      # At this point, pow2 = 2**p * 3**q 
      products.append(pow2) 
      pow2 = pow2 * 2 # this is like adding 1 to p 
     # now that p overflowed the maximum size, add 1 to q and start over 
     pow3 = pow3 * 3 

    # the Pratt sequence is the result of this process up to the given size 
    return sorted(products) 

print(generate_pratt(12))

来源

2014-09-21 23:03:16

如何实现Pratt间隙序列？ （Python，Shell Sort）

普拉特（大）

SEDB（大）

回答

相关问题

如何实现Pratt间隙序列？（Python，Shell Sort）