ค้นหาอักขระในตำแหน่งแรกและสลับอักขระที่เหลือกับอักขระตัวแรก เช่นเดียวกับใน ABC ในการวนซ้ำครั้งแรกจะมีการสร้างสามสตริง:ABC, BAC และ CBA โดยการสลับ A กับ A, B และ C ตามลำดับ ทำซ้ำขั้นตอนสำหรับอักขระที่เหลือ เช่น แก้ไขอักขระตัวที่สอง B เป็นต้น Nowswap อีกครั้งเพื่อกลับไปที่ตำแหน่งก่อนหน้า จาก ABC เราสร้าง ABC โดยตรึง B อีกครั้ง และเราย้อนรอยไปยังตำแหน่งก่อนหน้าและสลับ 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
