c＃getEnumerator（）の再帰バージョンの作成方法

https://stackoverflow.com/questions/8821814

27-10-2019
|

質問

getEnumerator（）の再帰バージョンを作成する方法について誰かが私にアドバイスを与えることができますか？有名なハノイの問題の塔私が持っている実際の問題に匹敵する例として役立つかもしれません。高さ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パラメーターを取り除くようです。これは、スタックを使用して簡単に実行できます。また、パラメーターを単一の変数に組み合わせたクラスの動きも導入しました。

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（）の体はどのように見えますか？誰かが私のためにこの謎を解決できますか？

以下は、作成したコンソールアプリケーションのCode.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 ();
    }
  }
}

解決

あなたのアプローチはかなり良いですが、あなたは問題をやや考えていると思います。一歩下がってみましょう。再帰アルゴリズムがあります：

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);
  } 
}

これは正しいですか？いいえ。私たちは何も返していませんが、まだコンソールにダンプしています。 イテレーターに何を与えたいですか？ イテレーターが得られることを願っています：

最初の再帰ステップに必要なすべての動き
現在の動き
2番目の再帰ステップに必要なすべての動き

したがって、アルゴリズムを変更して、次のことを生成します。

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手順を実行して完了します。そのため、再帰なしで問題を解決する傾向があります。

エクササイズ: ：再帰が行われないように、上のイテレーターブロックを書き直します まったく. 。明示的なスタックを使用するソリューションは、正しい方向へのステップですが、それでも再発します。再帰が行われないように適応できますか？

あなたが実装するクラスを書くことに屈した場合 IEnumerable<Move> 次に、上記のコードを簡単な方法で適応させることができます。

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

獲得リターンを使用して、列挙者を返すメソッドを実装できますまた列挙可能.

他のヒント

あなたの非再帰ソリューションは優れています - プッシュダウンオートマトンを構築する（本質的にスタックを備えた状態マシン）は、再帰ソリューションの反復バージョンを構築するための標準的な手法です。実際、これは、イテレーターと非同期ブロックのコードを生成する方法と非常に似ています。

ただし、この特定のケースでは、スイッチと現在の状態でプッシュダウンオートマトンの重い機械を引き出す必要はありません。あなたはこれを行うことができます：

IEnumerable<Move> MoveTowerConsole (int size, Needle start, Needle finish, Needle temp) 
{   
  if (size <= 0) yield break;
  var stack = new Stack<Work>();
  stack.Push(new Work(size, start, finish, temp));
  while(stack.Count > 0)
  {
    var current = stack.Pop();
    if (current.Size == 1) 
      yield return new Move(current.Start, current.Finish);
    else
    {
       // Push the work in the *opposite* order that it needs to be done.
       stack.Push(new Work(current.Size - 1, current.Temp, current.Finish, current.Start));
       stack.Push(new Work(1, current.Start, current.Finish, current.Temp));
       stack.Push(new Work(current.Size - 1, current.Start, current.Temp, current.Finish));

     }
}

現在の再帰ステップの後にどのような仕事をする必要があるかを既に正確に知っているので、3つの作業をスタックに置くためにスイッチを跳ね返す必要はありません。ただキュー全て特定のステップで一度にワークアップします。

非回復バージョン：

// Non-recursive version -- state engine
//rta.Push (State.Exit);
//parameters.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
//MoveTower3 ();

enum State { Init, Call1, Call2, Rtrn, Exit }

{  
  ...

  #region Non-recursive version -- state engine
  static void MoveTower3 ()
  {
    State s = State.Init;
    Move m = null;

    while (true)
      switch (s)
      {
        case State.Init:
          m = moveStack.Pop ();
          s = (m.n <= 0) ? State.Rtrn : State.Call1;
          break;
        case State.Call1:
          rta.Push (State.Call2); // where do I want to go after the call is finished
          moveStack.Push (m);    // save state for second call
          moveStack.Push (new Move (m.n-1, m.start, m.temp, m.finish)); // parameters
          s = State.Init;
          break;
        case State.Call2:
          m = moveStack.Pop ();  // restore state from just before first call
          Console.WriteLine (m);
          rta.Push (State.Rtrn);
          moveStack.Push (new Move (m.n-1, m.temp, m.finish, m.start));
          s = State.Init;
          break;
        case State.Rtrn:
          s = rta.Pop ();
          break;
        case State.Exit:
          return;
      }
  }
  #endregion

  #region Enumeration
  static IEnumerable<Move> GetEnumerable (int n)
  {
    Stack<Move> moveStack = new Stack<Move> ();
    Stack<State> rta = new Stack<State> (); // 'return addresses'
    rta.Push (State.Exit);
    moveStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
    State s = State.Init;
    Move m = null;

    while (true)
      switch (s)
      {
        case State.Init:
          m = moveStack.Pop ();
          s = (m.n <= 0) ? State.Rtrn : State.Call1;
          break;
        case State.Call1:
          rta.Push (State.Call2); // where do I want to go after the call is finished
          moveStack.Push (m);    // save state for second call
          moveStack.Push (new Move (m.n-1, m.start, m.temp, m.finish)); // parameters
          s = State.Init;
          break;
        case State.Call2:
          m = moveStack.Pop ();  // restore state from just before first call
          yield return m;
          rta.Push (State.Rtrn);
          moveStack.Push (new Move (m.n-1, m.temp, m.finish, m.start));
          s = State.Init;
          break;
        case State.Rtrn:
          s = rta.Pop ();
          break;
        case State.Exit:
          yield break;
      }
  }
  #endregion
}

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow