In tất cả hoán vị của chuỗi dùng ArrayList trong Java

Đề bài

Cho chuỗi độ dài n, in ra tất cả các hoán vị của chuỗi đó sử dụng ArrayList.

Ví dụ:

• Input: XYZ
• Output: XYZ, XZY, YXZ, YZX, ZXY, ZYX

Thuật toán

Sử dụng đệ quy: tách ký tự đầu, tạo hoán vị cho phần còn lại, sau đó chèn ký tự đầu vào mọi vị trí khả thi của mỗi hoán vị con.

Triển khai Java

import java.util.ArrayList;

public class Main {
    static void printArrayList(ArrayList<String> combo) {
        combo.remove(""); // loại bỏ chuỗi rỗng nếu có
        for (int i = 0; i < combo.size(); i++) {
            System.out.print(combo.get(i) + "\t");
        }
    }

    public static ArrayList<String> generatePermutation(String str) {
        if (str.length() == 0) {
            ArrayList<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        char ch = str.charAt(0);
        String subStr = str.substring(1);
        ArrayList<String> lastCombination = generatePermutation(subStr);
        ArrayList<String> newCombination = new ArrayList<>();
        for (String val : lastCombination) {
            for (int i = 0; i <= val.length(); i++) {
                newCombination.add(val.substring(0, i) + ch + val.substring(i));
            }
        }
        return newCombination;
    }

    public static void main(String[] args) {
        String str = "NOPQ";
        System.out.println("Các hoán vị của chuỗi:");
        printArrayList(generatePermutation(str));
    }
}

Kết quả

Các hoán vị của chuỗi:
NOPQ  ONPQ  OPNQ  OPQN  NPOQ  PNOQ  PONQ  POQN  NPQO  PNQO  PQNO  PQON
NOQP  ONQP  OQNP  OQPN  NQOP  QNOP  QONP  QOPN  NQPO  QNPO  QPNO  QPON

Phân tích độ phức tạp

• Thời gian: O(n! * n) - có n! hoán vị, mỗi hoán vị mất O(n) để xây dựng chuỗi.
• Không gian: O(n! * n) - lưu trữ tất cả hoán vị.

Lưu ý: Với chuỗi dài (>10 ký tự), số lượng hoán vị rất lớn, có thể gây tràn bộ nhớ.