C# 如何制作 GetEnumerator() 的递归版本

Question

有人可以就如何创建递归版本的 GetEnumerator() 给我建议吗？家喻户晓Towers of Hanoi problem可以作为与我遇到的实际问题相当的例子。显示高度为 n 的一堆磁盘的所有移动的简单算法是:

void MoveTower0 (int n, Needle start, Needle finish, Needle temp)
{
  if (n > 0)
  {
    MoveTower0 (n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTower0 (n - 1, temp, finish, start);
  }
}

我真正想做的是设置一个实现 IEnumerable 的 HanoiTowerMoves 类，它使我能够按如下方式迭代所有移动:

foreach (Move m in HanoiTowerMoves) Console.WriteLine (m);

实现 GetEnumerator() 的第一步似乎是摆脱 MoveTower 参数。这可以通过使用堆栈轻松完成。我还引入了一个 Move 类，它将参数组合到一个变量中。

class Move
{
  public int N { private set; get; }
  public Needle Start { private set; get; }
  public Needle Finish { private set; get; }
  public Needle Temp { private set; get; }

  public Move (int n, Needle start, Needle finish, Needle temp)
  {
    N = n;
    Start = start;
    Finish = finish;
    Temp = temp;
  }

  public override string ToString ()
  {
    return string.Format ("Moving disk from {0} to {1}", Start, Finish);
  }
}

现在 MoveTower 可以重写如下:

void MoveTower1 ()
{
  Move m = varStack.Pop ();

  if (m.N > 0)
  {
    varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
    MoveTower1 ();
    Console.WriteLine (m);
    varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
    MoveTower1 ();
  }
}

这个版本必须按如下方式调用:

varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
MoveTower1 ();

可迭代版本的下一步是实现类:

class HanoiTowerMoves : IEnumerable<Move>
{
  Stack<Move> varStack;
  int n; // number of disks

  public HanoiTowerMoves (int n)
  {
    this.n = n;
    varStack = new Stack<Move> ();
  }

  public IEnumerator<Move> GetEnumerator ()
  {
    // ????????????????????????????  }

  // required by the compiler:
  IEnumerator IEnumerable.GetEnumerator ()
  {
    return GetEnumerator ();
  }
}

现在对我来说最大的问题是:GetEnumerator () 的主体是什么样的？有人能为我解开这个谜团吗？

下面是我创建的控制台应用程序的 Program.cs 的代码。

using System;
using System.Collections.Generic;
using System.Collections;

/* Towers of Hanoi
 * ===============
 * Suppose you have a tower of N disks on needle A, which are supposed to end up on needle B.
 * The big picture is to first move the entire stack of the top N-1 disks to the Temp needle,
 * then move the N-th disk to B, then move the Temp stack to B using A as the new Temp needle.
 * This is reflected in the way the recursion is set up.
 */

namespace ConsoleApplication1
{
  static class main
  {
    static void Main (string [] args)
    {
      int n;
      Console.WriteLine ("Towers of Hanoi");

      while (true)
      {
        Console.Write ("\r\nEnter number of disks: ");

        if (!int.TryParse (Console.ReadLine (), out n))
        {
          break;
        }

        HanoiTowerMoves moves = new HanoiTowerMoves (n);
        moves.Run (1); // algorithm version number, see below
      }
    }
  }

  class Move
  {
    public int N { private set; get; }
    public Needle Start { private set; get; }
    public Needle Finish { private set; get; }
    public Needle Temp { private set; get; }

    public Move (int n, Needle start, Needle finish, Needle temp)
    {
      N = n;
      Start = start;
      Finish = finish;
      Temp = temp;
    }

    public override string ToString ()
    {
      return string.Format ("Moving disk from {0} to {1}", Start, Finish);
    }
  }

  enum Needle { A, B, Temp }

  class HanoiTowerMoves : IEnumerable<Move>
  {
    Stack<Move> varStack;
    int n;            // number of disks

    public HanoiTowerMoves (int n)
    {
      this.n = n;
      varStack = new Stack<Move> ();
    }

    public void Run (int version)
    {
      switch (version)
      {
        case 0: // Original version
          MoveTower0 (n, Needle.A, Needle.B, Needle.Temp);
          break;

        case 1: // No parameters (i.e. argument values passed via stack)
          varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
          MoveTower1 ();
          break;

        case 2: // Enumeration
          foreach (Move m in this)
          {
            Console.WriteLine (m);
          }

          break;
      }
    }

    void MoveTower0 (int n, Needle start, Needle finish, Needle temp)
    {
      if (n > 0)
      {
        MoveTower0 (n - 1, start, temp, finish);
        Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
        MoveTower0 (n - 1, temp, finish, start);
      }
    }

    void MoveTower1 ()
    {
      Move m = varStack.Pop ();

      if (m.N > 0)
      {
        varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
        MoveTower1 ();
        Console.WriteLine (m);
        varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
        MoveTower1 ();
      }
    }

    public IEnumerator<Move> GetEnumerator ()
    {
      yield break; // ????????????????????????????
    }

    /*
      void MoveTower1 ()
      {
        Move m = varStack.Pop ();

        if (m.N > 0)
        {
          varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
          MoveTower1 ();
          Console.WriteLine (m); ? yield return m;
          varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
          MoveTower1 ();
        }
      }
    */

    // required by the compiler:
    IEnumerator IEnumerable.GetEnumerator ()
    {
      return GetEnumerator ();
    }
  }
}

Answer 1

您的方法很好，但我认为您在某种程度上考虑了这个问题。让我们退后一步。你有一个递归算法:

void MoveTowerConsole (int n, Needle start, Needle finish, Needle temp) 
{   
  if (n > 0)   
  {
    MoveTowerConsole (n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTowerConsole (n - 1, temp, finish, start);
  } 
} 

算法的输出是一堆控制台输出。相反，假设您希望算法的输出是将要输出到控制台的字符串序列。让我们来推理一下这样的方法会是什么样子。

首先，我们将重命名它。其次，它的返回类型不能为空。必须是 IEnumerable<string> :

IEnumerable<string> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    MoveTower(n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTower(n - 1, temp, finish, start);
  } 
}

这样对吗？不，我们没有返回任何东西，我们仍然在向控制台转储。 我们希望迭代器产生什么？我们希望迭代器产生:

• 第一个递归步骤所需的所有 Action
• 当前的着法
• 第二个递归步骤所需的所有 Action

因此我们修改算法以产生这些:

IEnumerable<string> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    foreach(string move in MoveTower(n - 1, start, temp, finish))
        yield return move;
    yield return string.Format("Moving disk from {0} to {1}", start, finish);
    foreach(string move in MoveTower(n - 1, temp, finish, start))
        yield return move;
  } 
}

我们完成了!就这么简单。无需定义整个类即可将递归算法转换为递归枚举器；让编译器为您完成这项工作。

如果你想把它变成一个枚举“移动”的方法，那么这样做:

IEnumerable<Move> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    foreach(Move move in MoveTower(n - 1, start, temp, finish))
        yield return move;
    yield return new Move(start, finish);
    foreach(Move move in MoveTower(n - 1, temp, finish, start))
        yield return move;
  } 
}

现在，我会根据效率批评这段代码。通过以这种方式制作递归枚举器，您所做的就是构建一个 n 个枚举器链。当你需要下一个项目时，顶部的枚举器调用下一个枚举器调用下一个枚举器......向下到底部，n 深。所以现在每一步实际上需要n步才能完成。出于这个原因，我倾向于不使用递归来解决问题。

练习:重写上面的迭代器 block ，使其完全不进行递归。您使用显式堆栈的解决方案是朝着正确方向迈出的一步，但它仍然会进行递归。您能否调整它以便不进行递归？

如果您一心想编写一个实现 IEnumerable<Move> 的类那么您可以直接修改上面的代码:

class MoveIterator : IEnumerable<Move>
{
    public IEnumerator<Move> GetEnumerator()
    {
        foreach(Move move in MoveTower(whatever))
            yield return move;
    }

您可以使用 yield return 来实现返回枚举数或可枚举数的方法。