C# Как сделать рекурсивную версию GetEnumerator()
Может кто-нибудь дать мне совет о том, как создать рекурсивную версию 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);
}
}
Что я на самом деле хочу сделать, так это создать класс HanoiTowerMoves, который реализует IEnumerable и который позволяет мне выполнять итерации по всем шагам следующим образом:
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 ();
}
}
}
3 ответа
Ваш подход довольно хорош, но я думаю, что вы несколько обдумали проблему. Давайте сделаем шаг назад. У вас есть рекурсивный алгоритм:
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);
}
}
Это правильно? Нет. Мы ничего не возвращаем, мы все еще выкидываем на консоль. Что мы хотим, чтобы итератор дал? Мы хотим, чтобы итератор дал:
- все ходы, необходимые для первого рекурсивного шага
- текущий ход
- все ходы, необходимые для второго рекурсивного шага
Поэтому мы модифицируем алгоритм, чтобы получить те:
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 шагов. По этой причине я был бы склонен решить проблему без рекурсии.
Упражнение: Перепишите блок итератора выше, чтобы он вообще не выполнял рекурсию. Ваше решение, использующее явный стек, является шагом в правильном направлении, но все равно выполняет рекурсию. Можете ли вы адаптировать его так, чтобы рекурсия не выполнялась?
Если вы хотите написать класс, который реализует IEnumerable<Move> тогда вы можете адаптировать приведенный выше код простым способом:
class MoveIterator : IEnumerable<Move>
{
public IEnumerator<Move> GetEnumerator()
{
foreach(Move move in MoveTower(whatever))
yield return move;
}
Вы можете использовать yield return для реализации метода, который возвращает перечислитель или перечислимый.
Ваше нерекурсивное решение хорошо - создание автомата сжатия (по сути, конечного автомата со стеком) является стандартной техникой для построения итерационной версии рекурсивного решения. И на самом деле это очень похоже на то, как мы генерируем код для блоков итераторов и асинхронных блоков.
Однако в этом конкретном случае вам не нужно извлекать тяжелую технику из автоматов с переключателем и текущим состоянием. Вы можете просто сделать это:
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));
}
}
Вы уже точно знаете, какую работу вам нужно выполнить после текущего рекурсивного шага, поэтому нет необходимости прыгать вокруг переключателя, чтобы поместить три бита работы в стек. Просто поставьте в очередь всю работу за один шаг.
Нерекурсивная версия:
// 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
}