C # Comment faire une version récursive de GetEnumerator ()

Question

Quelqu'un peut-il me donner des conseils sur la façon de créer une version récursive de GetEnumerator ()? Le bien connu peut servir d'exemple qui est comparable au problème réel I avoir. Un algorithme simple pour montrer tous les mouvements pour une pile de disques de hauteur n est:

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

Ce que je veux vraiment faire est mis en place une HanoiTowerMoves de classe qui implémente IEnumerable et qui me permet d'itérer sur tous les mouvements comme suit:

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

La première étape vers une mise en œuvre GetEnumerator () semble se débarrasser des paramètres de MoveTower. Cela peut facilement être fait en utilisant une pile. J'ai également introduit un mouvement de classe qui combine les paramètres en une seule variable.

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 peut être réécrite comme suit:

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

Cette version doit être appelée comme suit:

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

La prochaine étape vers une version itérables est de mettre en œuvre la classe:

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

Maintenant, pour moi, la grande question est: qu'est-ce que le corps de GetEnumerator () ressembler? Quelqu'un peut-il résoudre ce mystère pour moi?

Voici le code de Program.cs de l'application de la console que j'ai créé.

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

Votre approche est assez bonne, mais je pense que vous Overthinking un peu le problème. Prenons un pas en arrière. Vous avez un algorithme récursif:

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

La sortie de l'algorithme est un groupe de sortie de la console. Supposons maintenant que vous souhaité la sortie de l'algorithme à la séquence de chaînes va être à la console. la raison Let à ce qu'une telle méthode ressemblerait.

Tout d'abord, nous allons le renommer. En second lieu, son type de retour ne peut pas être vide. Il doit être 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);
  } 
}

Est-ce exact? Non, nous ne sommes pas quoi que ce soit revenions, nous le dumping encore à la console. ? Qu'est-ce que nous souhaitons la iterator Céder Nous souhaitons iterator céder:

• tous les mouvements nécessaires pour la première étape récursive
• le mouvement actuel
• tous les mouvements nécessaires pour la deuxième étape récursive

Nous modifions l'algorithme pour obtenir ceux-ci:

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

Et nous fait! Aussi simple que ça. Il n'y a pas besoin d'être la définition d'une classe entière de transformer un algorithme récursif dans un recenseur récursive; laissez le compilateur faire ce travail pour vous.

Si vous voulez changer cela en une méthode qui « bouge » ENUMERE, puis le faire:

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

Maintenant, je critique ce code sur la base de l'efficacité. En faisant des recenseurs récursives de cette manière, ce que vous faites est la construction d'une chaîne de recenseurs n. Lorsque vous avez besoin de l'élément suivant, le recenseur haut appelle la prochaine recenseur appelle la prochaine recenseur ... vers le bas, n profond. Donc, chaque étape prend maintenant en fait n étapes pour terminer. Je serais enclin à résoudre le problème sans récursion pour cette raison.

Exercice : Réécrire le bloc itérateur ci-dessus pour qu'il ne fait pas récursivité tout . Votre solution qui utilise une pile explicite est un pas dans la bonne direction, mais il fait encore récursivité. Pouvez-vous l'adapter afin que ne récursion est fait?

Si vous êtes plié à écrire une classe qui implémente IEnumerable<Move> vous pouvez adapter le code ci-dessus d'une manière simple:

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

Vous pouvez utiliser le retour de rendement pour mettre en œuvre une méthode qui renvoie un recenseur ou un dénombrable .

Answer 2

Votre solution non récurrente est bon - la construction d'un automate à pile (une machine d'état avec une pile, essentiellement) est une technique standard pour la construction d'une version itérative d'une solution récursive. En fait, ce qui est très similaire à la façon dont nous générons code pour iterator et async blocs.

Cependant, dans ce cas spécifique que vous n'avez pas besoin de retirer la machinerie lourde d'un automate à pile avec un commutateur et un état actuel. Vous pouvez simplement faire ceci:

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

     }
} 

Vous savez déjà exactement ce que vous travaillez devez faire après l'étape récursive actuelle, il n'y a donc pas besoin de rebondir autour d'un interrupteur pour mettre les trois bits de travail sur la pile. Il suffit de file d'attente tous le travail à la fois pour jusqu'à une étape donnée.

Answer 3

Version non récursif:

// 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
}