Làm cách nào để tìm tất cả các hoán vị của chuỗi trong JavaScript?

Dưới đây là các hoán vị của xâu ABC.
ABC ACB BAC BCA CBA CAB

Điều này có thể được giải quyết bằng thuật toán đệ quy và câu hỏi được hỏi nhiều nhất trong các cuộc phỏng vấn,

function permute(str, l, r) {
    if (l == r)
        console.log(str);
    else {

        for (let i = l; i <= r; i++) {
            str = swap(str, l, i);
            permute(str, l + 1, r);
            str = swap(str, l, i);
        }

    }
}

function swap(str, i, j) {
    let strArr = str.split("");
    let temp = strArr[i];
    strArr[i] = strArr[j]
    strArr[j] = temp;
    return strArr.join("");
}

let str = "ABC";
let n = str.length - 1;
permute(str, 0, n);

Thuật toán. Quay lui
Độ phức tạp về thời gian. O(n*n. )

BÀI LIÊN QUAN

Cho một chuỗi ngắn A và một chuỗi dài hơn B. Tìm tất cả các hoán vị của A xảy ra trên B. Chúng tôi giả sử rằng cả hai chuỗi chỉ chứa các ký tự ASCII

Ví dụ

A = “abcd“

B = “______5“

Kết quả = [“cdab”, “abcd”, “dcba”]

Giải pháp Brute Force

procdure getAllPermutations(a, b)
1. permutations = [] // array of all a permutations
2. result = [] // empty array
3. for i = 0 to b.length
   A. if permutations index of b.substring(i, a.length) > -1
      A.1 push b.substring(i, a.length) to result
4 return result

Triển khai JavaScript

Độ phức tạp về thời gian của một giải pháp ngây thơ để tạo ra tất cả các hoán vị của một chuỗi ít nhất sẽ là cấp số nhân, cụ thể là O(n. ), trong đó n là độ dài của chuỗi. Điều này là do có n. (n giai thừa) các hoán vị có thể có của một chuỗi có n ký tự. Ví dụ: chuỗi có 4 ký tự thì có 4. = 24 hoán vị và một chuỗi có 5 ký tự có 5. = 120 hoán vị

[
    'abcd', 'abdc', 'acbd',
    'acdb', 'adbc', 'adcb',
    'bacd', 'badc', 'bcad',
    'bcda', 'bdac', 'bdca',
    'cabd', 'cadb', 'cbad',
    'cbda', 'cdab', 'cdba',
    'dabc', 'dacb', 'dbac',
    'dbca', 'dcab', 'dcba'
  ]

Độ phức tạp lần này không hiệu quả lắm, đặc biệt đối với các chuỗi lớn hơn, vì số lượng hoán vị tăng rất nhanh với kích thước của chuỗi. Có nhiều thuật toán hiệu quả hơn để tạo các hoán vị có độ phức tạp thời gian thấp hơn, chẳng hạn như thuật toán Heap, có độ phức tạp thời gian là O(n * n. ), hoặc thuật toán Steinhaus–Johnson–Trotter, có độ phức tạp thời gian là O(n * n). Các thuật toán này có thể phù hợp hơn để tạo hoán vị của các chuỗi lớn hơn

Hãy thử chạy triển khai JS này khi một. chiều dài >= 10 và có thể bạn sẽ gặp lỗi hết thời gian chờ

thuật toán tối ưu hóa

Để tối ưu hóa thuật toán của chúng tôi, chúng tôi có thể thực hiện một cái gì đó tương tự như thuật toán Rabin-Karp. Cũng giống như nhiều thuật toán thời gian chạy hàm mũ, chẳng hạn như thuật toán dãy Fibonacci nổi tiếng, chúng ta có thể cải thiện thuật toán này bằng cách triển khai bảng băm

nền toán học

Gọi S = {A_1, …, A_n} là một danh sách nhiều tập hợp có kích thước N chỉ chứa các số nguyên tố. Gọi tổng các số trong S bằng một số nguyên Q. Khi đó S là tập hợp nhiều nguyên tố hoàn toàn duy nhất có thể có kích thước N, các phần tử của chúng có thể tổng bằng Q

Ephraim Rothschild

Điều này cho phép chúng ta gán mỗi ký tự cho một số nguyên tố, trong đó số nguyên tố là khóa băm, tổng của tất cả các hoán vị của các khóa ký tự chuỗi ngắn hơn là bằng nhau. Bây giờ, điều duy nhất còn lại là kiểm tra xem tổng các chuỗi con trên chuỗi dài hơn có bằng tổng của chuỗi sắp xếp không

Triển khai mã giả

procedure getAllPermutations(a, b)
1. result = []
2. smallHash = primes[a[0]] + primes[a[1]] .. + primes[a[a.length]]
3. left = 0, right = shorter.length
4. currentHash = primes[a[0]] + primes[a[1]] .. + primes[a[a.length]]
5. while right <= b.length
   A. if currentHash == smallHash
      A1. result.append(longer.substring(left, right))
   B. currentHash -= primes[b.charAt(left++)]
   C. if right < b.length
      C1. currentHash += primes[b.charAt(right)]
   D. right++
6. return result

Bỏ các hằng số, chúng tôi hoàn thành nó trong thời gian tuyến tính – O(b). Lưu ý rằng các hằng số, trong trường hợp này, có thể có ảnh hưởng đáng kể đến hiệu suất của thuật toán, nhưng dù sao, hiệu suất của thuật toán này sẽ tốt hơn nhiều so với thuật toán ngây thơ của chúng ta

Làm cách nào để tìm hoán vị trong JavaScript?

Làm cách nào để lấy tất cả các đảo chữ của một chuỗi JavaScript?

Làm cách nào để tạo hoán vị của một mảng trong js?