โจทย์: สร้าง permutations ทั้งหมดของสตริง โดยไม่ซ้ำ (distinct)
สตริงที่มีตัวอักษรซ้ำ เช่น "mnqm" ต้องกรอง permutations ซ้ำออก
ตัวอย่างโค้ด (Recursive + Set)
import java.util.*;
public class Demo {
// ใช้ Set เพื่อกรอง duplicates อัตโนมัติ
static Set distinctPermutations(String str) {
Set result = new LinkedHashSet<>(); // รักษาลำดับ
permute(str, 0, str.length() - 1, result);
return result;
}
static void permute(String str, int l, int r, Set result) {
if (l == r) {
result.add(str);
return;
}
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
permute(str, l + 1, r, result);
str = swap(str, l, i); // backtrack
}
}
static String swap(String str, int i, int j) {
char[] arr = str.toCharArray();
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return new String(arr);
}
public static void main(String[] args) {
String input = "mnqm";
System.out.println("Distinct permutations of \"" + input + "\":");
Set perms = distinctPermutations(input);
for (String s : perms) {
System.out.println(s);
}
System.out.println("Total: " + perms.size());
}
}
ผลลัพธ์
Distinct permutations of "mnqm": mnqm nmqm nqmm mqnm qmnm qnmm mqmn qmmn mnmq nmmq mmnq mmqn Total: 12
คำอธิบาย: ใช้ LinkedHashSet เก็บผลลัพธ์ - กรองซ้ำอัตโนมัติ + รักษาลำดับการเพิ่ม ใช้ backtracking swap characters
Complexity
- Time: O(n! × n) - n! permutations แต่ละอัน copy string O(n)
- Space: O(n! × n) - เก็บทุก permutation
- สำหรับสตริงยาว > 10 ควรใช้ iterator แบบ lazy (nextPermutation algorithm)
