×

Tạo Tất Cả Các Hoán Vị Của Một Chuỗi Trong JavaScript

Avatar of luongtu
luongtu 9 Views

Hoán vị của một chuỗi là tất cả các cách sắp xếp khác nhau của các ký tự trong chuỗi đó. Dưới đây là cách tạo tất cả các hoán vị của một chuỗi trong JavaScript bằng cách sử dụng đệ quy.

Mã Nguồn:

Phương Pháp 1: Sử Dụng Đệ Quy

function permute(str) {
    let results = [];

    if (str.length === 0) return [''];

    for (let i = 0; i < str.length; i++) {
        let char = str[i];
        let remainingChars = str.slice(0, i) + str.slice(i + 1);
        let permutations = permute(remainingChars);
        for (let perm of permutations) {
            results.push(char + perm);
        }
    }

    return results;
}

// Ví dụ kiểm tra
console.log(permute("abc"));
// Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

Phương Pháp 2: Sử Dụng Thuật Toán Heap

function heapPermutation(a, size, n, results) {
    if (size === 1) {
        results.push(a.join(''));
        return;
    }

    for (let i = 0; i < size; i++) {
        heapPermutation(a, size - 1, n, results);

        if (size % 2 === 1) {
            [a[0], a[size - 1]] = [a[size - 1], a[0]];
        } else {
            [a[i], a[size - 1]] = [a[size - 1], a[i]];
        }
    }
}

function permuteHeap(str) {
    let results = [];
    let arr = str.split('');
    heapPermutation(arr, arr.length, arr.length, results);
    return results;
}

// Ví dụ kiểm tra
console.log(permuteHeap("abc"));
// Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

Giải Thích:

  1. Phương Pháp Đệ Quy:

    • Cơ sở Đệ Quy: Nếu chuỗi dài 0, trả về một mảng chứa chuỗi rỗng.
    • Ghi nhận Ký Tự: Lặp qua tất cả các ký tự của chuỗi, tách ký tự ra và gọi đệ quy với phần còn lại của chuỗi.
    • Kết Hợp Hoán Vị: Kết hợp ký tự hiện tại với tất cả các hoán vị của phần còn lại để tạo ra tất cả các hoán vị.

  2. Phương Pháp Heap:

    • Heap's Algorithm: Thuật toán Heap được sử dụng để sinh tất cả các hoán vị của một chuỗi.
    • Ghi nhận Ký Tự: Sử dụng một phương pháp hoán đổi để tạo ra tất cả các hoán vị.

Tổng Quan:

  • Hoán Vị: Tất cả các cách sắp xếp ký tự trong chuỗi.
  • Đệ Quy: Phương pháp đơn giản, dễ hiểu, nhưng có thể kém hiệu quả cho chuỗi dài.
  • Thuật Toán Heap: Hiệu quả hơn cho việc tạo hoán vị và không cần nhiều bộ nhớ phụ.

Ví Dụ Thực Tế:

console.log(permute("abc")); // ["abc", "acb", "bac", "bca", "cab", "cba"]
console.log(permuteHeap("abc")); // ["abc", "acb", "bac", "bca", "cab", "cba"]

Trong ví dụ trên, cả hai phương pháp tạo ra tất cả các hoán vị của chuỗi "abc".

Comments

Bài viết liên quan