如何使用 C# 通过回溯找到字符串的所有排列?
csharpserver side programmingprogramming更新于 2025/4/17 5:22:17
找到第一个位置的字符，并将该字符的其余部分与第一个字符交换。与 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
