無遞歸的字符串排列

這裏是遞歸的代碼。
你們可以給我提供關於如何使用迭代方法來實現這一點的輸入嗎？無遞歸的字符串排列

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

無遞歸的字符串排列

回答

相關問題