了解字符串排列递归情况之间的区别

Question

   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);
        }
 }

两者都打印出完全相同的东西，区别在于第一个在permute递归调用之后调用swap方法。根据我在网上阅读的内容，底部交换是“回溯” 回到以前的情况，但它可以很好地回溯而无需进行额外的交换？有人可以解释我缺少或不理解的内容吗？对我来说，最后一个对我来说更有意义。

Answer 1

所以我只是浪费了 5 分钟研究排列算法...

回溯仅在使用直接内存或引用时有用。由于 strings 在 C# 中是 immutable，更改不会通过递归堆栈推回，所以 back tracking 对于将状态返回到之前的 pre-recursed 状态没有用（本质上什么都没有改变）。 =14=]

但是，如果您使用 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

总而言之，如果您不使用直接内存或引用，它就没有用。

了解字符串排列递归情况之间的区别

understanding the difference Between string permutation Recursive cases

c#

string

recursion

permutation