如何实现普拉特间隙序列？（Python，Shell排序）

Question

我必须用Python编写一个shell sort程序，但同时我必须有一个程序，它使用一些特殊的间隙序列来创建文本文件，这就是我的shell sort将得到它的间隙编号的地方。在

在Wikipedia（http://en.wikipedia.org/wiki/Shellsort）上，Pratt序列的方程是：“形式为2^p*3^q的连续数”，它产生1,2,3,4,6,8,9,12，。。。在

我不知道如何实现，基本上p和Q是什么？在

最坏情况下的时间复杂度为O（Nlog^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)

普拉特（大）

^{pr2}$

SedB（大）

    main()

Answer 1

http://oeis.org/A003586

罗伯特·威尔逊的观察结果可用于筛选数字
但速度太慢了O（n^2）
Mathematica代码看起来不错，可以生成
在不到O（n）时间内对Pratt序列进行排序

unit queue;
interface
   type pfifo_node = ^fifo_node;
        fifo_node = record
                data:longint;
                next:pfifo_node;
             end;
        fifo_pointers = record
                    head,tail:pfifo_node;
                 end;

procedure queue_init(var fifo:fifo_pointers);
function  queue_isEmpty(fifo:fifo_pointers):boolean;
procedure enqueue(var fifo:fifo_pointers;d:longint);
procedure dequeue(var fifo:fifo_pointers);
procedure print_queue(fifo:fifo_pointers);

implementation

procedure queue_init(var fifo:fifo_pointers);
begin
  fifo.head := NIL;
  fifo.tail := NIL;
end;

function  queue_isEmpty(fifo:fifo_pointers):boolean;
begin
  queue_isEmpty := ((fifo.head = NIL) and (fifo.tail = NIL));
end;

procedure enqueue(var fifo:fifo_pointers;d:longint);
var new_node:pfifo_node;
begin
  new(new_node);
  new_node^.data := d;
  new_node^.next := NIL;
  if(fifo.head = NIL) then
  begin
    fifo.head := new_node;
    fifo.tail := new_node;
  end
  else
  begin
    fifo.tail^.next := new_node;
    fifo.tail := new_node;
  end;
end;

procedure dequeue(var fifo:fifo_pointers);
var tmp:pfifo_node;
begin
  if(fifo.head <> NIL)then
  begin
    tmp := fifo.head^.next;
    dispose(fifo.head);
    fifo.head := tmp;
    if(tmp = NIL)then
      fifo.tail := NIL;
  end;
end;

procedure print_queue(fifo:fifo_pointers);
var tmp:pfifo_node;
    f:text;
begin
  assign(f,'');
  rewrite(f);   
  tmp := fifo.head;
  while(tmp <> NIL) do
  begin
    write(f,tmp^.data,' ');
    tmp := tmp^.next;
  end;
  writeln(f);
  close(f);
end;

begin

end.

program PrattGenerator;
uses crt,queue;

var fifo:fifo_pointers;
    n,pow3:longint;
    err:integer;
    aux:pfifo_node;

begin
  val(ParamStr(1),n,err);
  queue_init(fifo);
  enqueue(fifo,1);
  pow3 := 3;
  aux := fifo.head;
  while(fifo.tail^.data <= n) do
  begin
    if(2*aux^.data < pow3) then
    begin
      enqueue(fifo,2*aux^.data);
      aux := aux^.next;
    end
    else
    begin
      enqueue(fifo,pow3);
      pow3 := pow3 * 3;
    end;
  end;
  print_queue(fifo);
  while not queue_isEmpty(fifo) do
     dequeue(fifo);
end.

为了进行比较，我将介绍Damian的解决方案

^{pr2}$

我们可以使用堆栈来反转元素的顺序
不需要为堆栈创建新节点
我们可以尝试从现有队列节点构建堆栈

Answer 2

在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模拟这个表的生成。在

^{pr2}$