无递归的字符串排列

这里是递归的代码。
你们可以给我提供关于如何使用迭代方法来实现这一点的输入吗？无递归的字符串排列

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; 

      } 

     } 
    } 
}

来源

2009-07-17 Learner

这篇文章是对数学比较重，但可能帮帮忙：
http://msdn.microsoft.com/en-us/magazine/cc163513.aspx

综上所述，您使用factoradics枚举词法顺序排列。如果这对你来说听起来像希腊语，你并不孤单。

现在，这是正确的方式来做到这一点（至少直到一个数学博士算出更好的东西）。但我怀疑这是他们在面试中寻找的。更可能的是，他们正在寻找一种理解，即任何递归问题都是堆栈问题，它只是使用程序的调用堆栈而不是构建它自己的堆栈问题。

所以你可以将任何递归代码转换为迭代，方法是先取一个堆栈，按下初始值，然后在堆栈非空时循环。在循环内部，您可以弹出下一个值，在递归函数中进行相同的计算，并在您进行递归调用的任何地方进行推送。

来源

2009-07-17 21:24:03

耶稣，这是一些硬核希腊。我在采访中总是对这些问题感到绝望。希望这是一个加密工作。 – annakata 2009-07-17 21:29:01

事实根据方法的工作量比根据文章预计的要少。许多Project Euler问题我不得不使用类似的方法。

string str = "abcd"; 

Func<int, int> factorial = n => 
    Enumerable.Range(1, n) 
    .Aggregate((i, j) => i * j); 
Func<int, int, int[]> tofactoradic = (n, strLength) => 
    Enumerable.Range(1, strLength) 
    .Reverse() 
    .Select(i => { var m = n; n /= i; return m % i; }) 
    .ToArray(); 
Func<int[], string, string> Apply = (f, s) => { 
    var chars = s.ToList(); 
    var result = ""; 
    for (int i = 0; i < s.Length; i++) { 
     result += chars[f[i]]; 
     chars.RemoveAt(f[i]); 
    } 
    return result; 
}; 

int max = factorial(str.Length); 
for (int i = 0; i < max; i++) { 
    var f = tofactoradic(i, str.Length); 
    Console.WriteLine(Apply(f, str)); 
}

来源

2009-07-17 22:25:11 Jimmy

无递归的字符串排列

回答

相关问题