没有递归的字符串排列

Question

这是递归代码.
你们能否就如何使用迭代方法实现这一点给出意见？

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PermAndComb
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "abcd";
            Permutation(s);
            Console.ReadKey();

        }

        public static void Permutation(string s)
        {
            int len = s.Length;
            char [] inStr  = s.ToCharArray();
            StringBuilder outStr = new StringBuilder();
            bool[] used = new bool[len];

            doPermute(inStr, outStr,used, len, 0);

        }

        public static void doPermute(char[] instr, StringBuilder outStr,bool [] used, int len, int level)
        {
            if (level == len)
            {
                Console.WriteLine(outStr.ToString());
                return;
            }

            for (int i = 0; i < len; i++)
            {
                if (used[i]) continue;
                outStr.Append(instr[i]);
                used[i] = true;
                doPermute(instr, outStr, used, len, level + 1);
                used[i] = false;
                outStr.Length = outStr.Length - 1;

            }

        }
    }
}

Answer 1

这篇文章在数学上相当沉重,但可能有所帮助:http:
//msdn.microsoft.com/en-us/magazine/cc163513.aspx

总之,您使用factoradics来枚举词汇顺序中的排列.如果这听起来像希腊语,那么你并不孤单.

现在,这是正确的方法(至少在数学博士得出更好的东西之前).但我怀疑这是他们在采访中寻找的东西.更有可能的是,他们正在寻找一种理解,即任何递归问题也是一个堆栈问题,它只使用程序的调用堆栈而不是构建它自己的.

因此,您可以通过获取堆栈,推送初始值,然后在堆栈不为空时循环来将任何递归代码转换为迭代.在循环内部,你弹出下一个值,进行你在递归函数中所做的相同计算,并推送你所做的递归调用.