是否存在一种恒时间算法来增量生成希尔伯特点曲线?

Question

关于希尔伯特立方体的维基百科文章包括对希尔伯特曲线上任意点的任意索引进行编码/解码的函数。这些算法不是恒定时间的。是否存在一种恒时算法，给定曲线上的一个实际点(也许，还有一些必需的状态)，生成下一个点(和下一个状态)?

形式上，我想要一个类型State和一个元组(initialState, nextState) :: (State, State -> ((Nat, Nat), State)，这样nextState的每次应用都会给我们希尔伯特曲线的下一个点，并且这样nextState是最优的，这可能不是维基百科上呈现的算法的情况，因为它可能错过了我们在这里的增量计算的机会。说明:

data State = _
initialState :: State
initialState = _
-- This must be optimal
nextState :: State -> ((Nat, Nat), State)
nextState = _
-- Returns the `nth point` of the hilbert curve
hilbertPoint :: Nat -> (Nat, Nat)
hilbertPoint n = iterate (snd.nextState) initialState !! n

Answer 1

如果你的意思是"是否存在一种算法能够以每个顶点O(1)的代价生成希尔伯特曲线的顶点?"答案是肯定的。这是一个标准的递归练习。如果您有用于发出顶点的常用海龟图形原语，它看起来像这样:

-- Angle must be + or - 90.0 degrees.
procedure Hilbert(Order : in Natural;
                  Angle : in Float) is
   Step : constant Float := 1.0; -- length of base case edge
begin
   if Order > 0 then
      Turn(Angle);
      Hilbert(Order - 1, -Angle);
      Walk(Step);
      Turn(-Angle);
      Hilbert(Order - 1,  Angle);
      Walk(Step);
      Hilbert(Order - 1,  Angle);
      Turn(-Angle);
      Walk(Step);
      Hilbert(Order - 1, -Angle);
      Turn(Angle);
   end if;
end Hilbert;

用

初始化递归

Hilbert(7, 90.0);

得到七阶曲线

添加

既然您似乎对迭代器模式感兴趣，那么您可以使用上面的逻辑和带有生成器的语言(如Python或Ruby)，或者您可以使用通常的递归到迭代代码转换的技术自己实现生成器。