Nhờ giải thích thuật toán sinh hoán vị của Heap

Ban đầu thấy title tưởng là Heap sort, định vào hổ báo, ai dè “Giải thuật Heap” để brute force…
Search google mãi mới thấy

Em làm bài tập bình thường thôi anh,brute force nghe ghê quá

https://vascal.github.io/algo/permute
Đây là cách giải thích trong tiếng Việt, người ta giải thích cũng đến đây thôi chứ không biết nói sao.

Em mới học mỗi javascript nên đọc code mẫu ở trang anh bảo mà không hiểu lắm;
em có cái function viết bằng Javascript ở đây.mong anh và mọi người giải thích giúp

function gen(n){ // n  === arr.length( vd arr=["a","b","c"] )
if(n ===1){
  var x = arr.join("");
  permu.push(x); // permu =[];
  
}
else{
  for( var i = 0 ; i != n; i++){
    gen(n-1);
    swap(n % 2 ? 0 : i, n - 1);
  }
}

}

mới đọc tưởng cấu trúc dữ liệu Heap =))
mà sinh hoán vị xài đệ qui được rồi mà nhỉ?

Cái này cũng là quay lui thôi nhưng nó duyệt có vẻ nhanh hơn vì không bị hạn chế output.

Đầu tiên bạn giữ cố định phần tử cuối cùng và hoán vị phần còn lại. Sau đó bạn phải đổi chỗ nó với phần còn lại thì mới đủ. Hiểu sơ sơ thì nó như vậy. Vì sao phải chia trường hợp chẵn lẻ thì khó đây.

Đẹp nhất là thuật toán SJT (hay Johnson-Trotter), nhưng nhanh nhất vẫn là thuật toán của Heap.

cho mình hỏi tại sao lại nhanh nhỉ? cũng phải sinh đủ n! hoán vị mà nhỉ?

Còn dễ hiểu nhất là “thuật toán sinh hoán vị noz1995”:

- Cho trước một chuỗi n phần tử đầu vào
- Tạo ra một dãy sắp xếp ngẫu nhiên từ các phần tử đầu vào
- Làm đi làm lại bước trên đến khi nào đủ n! hoán vị khác nhau

Bài này dùng giải thuật battracking . Bạn xem chi tiết ở đây , có giải thích rõ ràng

GeeksforGeeks – 2 Aug 09

Write a program to print all permutations of a given string - GeeksforGeeks

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with… Read More »