การสร้าง Permutations ของสตริงใน Java (Recursion + Backtracking)

Permutation คืออะไร?

Permutation คือการจัดเรียงสมาชิกของเซตในลำดับต่างๆ สำหรับสตริงความยาว n มี permutation ทั้งหมด n! แบบ

ตัวอย่างโค้ด (Recursive Backtracking)

public class Demo { 
    static void printPermutations(String remaining, String prefix) { 
        // Base case: ไม่มีตัวอักษรเหลือ -> พิมพ์ prefix
        if (remaining.length() == 0) { 
            System.out.print(prefix + " "); 
            return; 
        } 
        
        // boolean array กันตัวอักษรซ้ำ (สำหรับสตริงที่มีตัวซ้ำ เช่น "aab")
        boolean[] used = new boolean[26]; // assuming lowercase a-z
        
        for (int i = 0; i < remaining.length(); i++) { 
            char ch = remaining.charAt(i); 
            
            // ข้ามตัวอักษรที่ใช้ไปแล้วในระดับนี้ (กัน duplicate permutations)
            if (used[ch - 'a']) continue; 
            used[ch - 'a'] = true; 
            
            // สร้างสตริงที่เหลือ (ลบตัวที่ i ออก)
            String nextRemaining = remaining.substring(0, i) + remaining.substring(i + 1); 
            
            // Recursive call: เพิ่ม ch เข้า prefix
            printPermutations(nextRemaining, prefix + ch); 
        } 
    } 
    
    public static void main(String[] args) { 
        String str = "hey"; 
        System.out.println("Permutations ของ \"" + str + "\":"); 
        printPermutations(str, ""); 
        System.out.println(); 
    } 
}

ผลลัพธ์

Permutations ของ "hey":
hey hye ehy eyh yhe yeh 

คำอธิบายอัลกอริทึม

1. Base case: ไม่มีตัวอักษรเหลือ → พิมพ์ prefix (permutation หนึ่งเสร็จ)
2. Loop ทุกตำแหน่ง: เลือกตัวอักษรแต่ละตัวเป็นตัวถัดไป
3. Skip duplicates: ใช้ boolean array กันการสร้าง permutation ซ้ำ (สำคัญสำหรับสตริงแบบ "aab")
4. Recursive call: ส่ง remaining (ลบตัวที่เลือกออก) และ prefix + ch

Trace สำหรับ "abc"

printPermutations("abc", "")
  i=0: ch='a', rem="bc" -> printPermutations("bc", "a")
    i=0: ch='b', rem="c" -> printPermutations("c", "ab")
      i=0: ch='c', rem="" -> PRINT "abc"
    i=1: ch='c', rem="b" -> printPermutations("b", "ac")
      i=0: ch='b', rem="" -> PRINT "acb"
  i=1: ch='b', rem="ac" -> printPermutations("ac", "b")
    ... -> "bac", "bca"
  i=2: ch='c', rem="ab" -> printPermutations("ab", "c")
    ... -> "cab", "cba"

ความซับซ้อน

Java 8+ Stream Approach

// เขียนเองยุ่ง ใช้ library หรือ iterative approach ดีกว่า
// Apache Commons: StringUtils.permutations() 
// Guava: Collections2.permutations(list)

Iterative Version (Heap's Algorithm) - ไม่ใช้ Recursion

public static void heapPermutation(int[] arr, int n, List result) { 
    if (n == 1) { 
        result.add(arr.clone()); 
        return; 
    } 
    for (int i = 0; i < n; i++) { 
        heapPermutation(arr, n - 1, result); 
        if (n % 2 == 0) swap(arr, i, n - 1); 
        else swap(arr, 0, n - 1); 
    } 
}

ข้อควรระวัง

• n! เติบโตเร็วมาก: 10! = 3.6M, 11! = 39M, 12! = 479M → ใช้ได้เฉพาะ n ≤ 10
• boolean[26] สมมติ lowercase a-z เท่านั้น ต้องปรับสำหรับ Unicode
• สำหรับ production ใช้ library ที่ทดสอบแล้ว

การพิมพ์จำนวนเต็มระหว่างสตริงใน Java: String Concatenation

เปลี่ยนชื่อไฟล์หลายไฟล์ใน Java: Rename Multiple Files