如何通过使用 C# 回溯找到字符串的所有排列？

• Z时代
• 2024-01-10
• 分类：综合

找到第一个位置的字符并将字符的其余部分与第一个字符交换。就像在 ABC 中一样，在第一次迭代中，通过分别将 A 与 A、B 和 C 交换，形成了三个字符串：ABC、BAC 和 CBA。对其余字符重复步骤，例如修复第二个字符 B 等。现在再次交换回到之前的位置。从 ABC 开始，我们通过再次固定 B 形成 ABC，我们回溯到之前的位置并将 B 与 C 交换。所以，现在我们得到了 ABC 和 ACB。

示例

using System;
namespace ConsoleApplication{
   public class BackTracking{
      public void StringPermutation(string word, int start, int end){
         if (start == end){
            Console.WriteLine(word);
         }
         else{
            for (int i = start; i <= end; i++){
               Swap(ref word, start, i);
               StringPermutation(word, start + 1, end);
               Swap(ref word, start, i);
            }
         }
      }
      private void Swap(ref string word, int start, int end){
         char[] arr = word.ToCharArray();
         char temp = arr[start];
         arr[start] = arr[end];
         arr[end] = temp;
         word = new string(arr);
      }
   }
   class Program{
      static void Main(string[] args){
         BackTracking b = new BackTracking();
         b.StringPermutation("ABC", 0, 2);
      }
   }
}

ABC
ACB
BAC
BCA
CBA
CAB

以上是 如何通过使用 C# 回溯找到字符串的所有排列？ 的全部内容， 来源链接： utcz.com/z/327467.html