Tìm ký tự ở vị trí đầu tiên và hoán đổi phần còn lại của ký tự với ký tự đầu tiên. Giống như trong ABC, trong lần lặp đầu tiên, ba chuỗi được hình thành:ABC, BAC và CBA bằng cách hoán đổi A với A, B và C tương ứng. Lặp lại bước cho các ký tự còn lại như sửa ký tự thứ hai B, v.v. Nowswap một lần nữa để quay lại vị trí cũ. từ ABC, chúng tôi hình thành ABC bằng cách sửa B một lần nữa, và chúng tôi quay trở lại vị trí cũ và hoán đổi B với C. Vì vậy, bây giờ chúng tôi có ABC và ACB.
Ví dụ
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);
}
}
} Đầu ra
ABC ACB BAC BCA CBA CAB