Cách tìm tất cả hoán vị của chuỗi bằng backtracking C#

Tìm ký tự ở vị trí đầu tiên và hoán đổi các ký tự còn lại với ký tự đầu. Ví dụ ABC, lần lặp đầu tạo 3 chuỗi: ABC, BAC, CBA bằng cách hoán đổi A với A, B, C tương ứng. Lặp lại cho các ký tự tiếp theo như cố định ký tự thứ 2 B... Hoán đổi lại để quay về vị trí trước. Từ ABC, ta tạo ABC bằng cách cố định B lại, quay lui và hoán đổi B với C. Giờ ta 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);
        }
    }
}

Kết quả

ABC ACB BAC BCA CBA CAB

Giải thích: Sinh tất cả 6 hoán vị của chuỗi "ABC" bằng thuật toán backtracking hoán đổi (swap). Độ phức tạp O(n!). Kỹ thuật: cố định vị trí i, hoán đổi với các vị trí j ≥ i, đệ quy, rồi hoán đổi ngược (backtrack).