Em xin chào các anh chị,hiện tại em đang học Javascript tren freecodecamp và em gặp bài toán cần sử dụng giải thuật Heap để tìm những biến thể hoán vị của một string.vd “abc” thì sẽ có “bac”,“cba”…
nhưng em đọc ở Wikipedia thì lại không hiểu rõ lắm vì có khá nhiều từ mới.Vậy anh chị nào có hiểu biết về giải thuật này hoặc hiểu được nó thì có thể giải thích lại cho em được không ạ.Em xin chân thành cảm ơn anh chị 
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 
1 Like
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.
1 Like
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ỉ?
1 Like
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.
1 Like
cho mình hỏi tại sao lại nhanh nhỉ? cũng phải sinh đủ n! hoán vị mà nhỉ?
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
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?