理解字串置換遞回案例之間的區別-有解無憂

   class RecursionExample
       {
           private static void doPermute(String str, int l, int r)
            {
                if (l == r)
                    Console.WriteLine(str);
                else
                {
                    for (int i = l; i <= r; i  )
                    {
                        str = swap(str, l, i);
                        doPermute(str, l   1, r);
                        str = swap(str, l, i);
                    }
                }
            }

            public static String swap(String a,int i, int j)
            {
                char temp;
                char[] charArray = a.ToCharArray();
                temp = charArray[i];
                charArray[i] = charArray[j];
                charArray[j] = temp;
                string s = new string(charArray);
                return s;
            }

            public static void Main()
            {
                String str = "ABC";
                int n = str.Length;
                doPermute(str, 0, n - 1);
            }
     }

相比

class RecursionExample
    {
        private static void doPermute(String str, int l, int r)
        {
            if (l == r)
                Console.WriteLine(str);
            else
            {
                for (int i = l; i <= r; i  )
                {
                    str = swap(str, l, i);
                    doPermute(str, l   1, r);
                }
            }
        }

        public static String swap(String a,int i, int j)
        {
            char temp;
            char[] charArray = a.ToCharArray();
            temp = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = temp;
            string s = new string(charArray);
            return s;
        }

        public static void Main()
        {
            String str = "ABC";
            int n = str.Length;
            doPermute(str, 0, n - 1);
        }
 }

兩者都列印出完全相同的東西，不同之處在于第一個在置換遞回呼叫之后呼叫交換方法。根據我在網上閱讀的內容，底部交換是“回溯”到前一個案例，但它可以很好地回溯而無需進行額外的交換？有人可以解釋我缺少或不理解的內容嗎？對我來說，底部對我來說更有意義。

uj5u.com熱心網友回復：

所以我只是浪費了 5 分鐘研究排列演算法......呃。

回溯僅在您使用直接記憶體或參考時有用。由于字串在C# 中是不可變的，因此更改不會通過遞回堆疊推回，因此回溯對于將狀態回傳到其先前的預先撤回狀態沒有用（本質上無論如何都不會改變）

但是，如果您使用ref（或陣列或類似的東西），您不僅會發現您的輸入發生了變異，更糟糕的是您會收到錯誤的結果。時期。

例子

private static void doPermute(ref string str, int l, int r)
{
   if (l == r)
      Console.WriteLine(str);
   else
   {
      for (int i = l; i <= r; i  )
      {
         str = swap(str, l, i);
         doPermute(ref str, l   1, r);
         str = swap(str, l, i);

      }
   }
}

帶回溯的輸出

ABC
ACB
BAC
BCA
CBA
CAB

沒有回溯的輸出

ABC
ACB
CAB
CBA
ABC
ACB

總之，如果您不使用直接記憶體或參考，則它沒有任何作用。

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/344880.html

標籤：C＃细绳递归排列

上一篇：我如何在golang中執行此遞回

下一篇：我需要將此頭遞回函式轉換為尾遞回