วิธีหาการเรียงสับเปลี่ยนทั้งหมดของสตริงโดยใช้ Backtracking ด้วย C#

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