Tiêu đề hơi khó hiểu ạ, cụ thể là ví dụ em có 3 chữ cái “a”, “b”, “c”. Em muốn in ra tất cả các trường hợp có thể từ 3 chữ cái này:
abc
acb
bac
bca
cab
cba
Các bác giúp em với ạ, em cảm ơn ạ.
Thuật toán in ra tất cả các chuỗi có thể sắp xếp được từ 1 mảng có sẵn
Cái này thì chắc là liệt kê tất cả các hoán vị trong mảng rồi:
2 Likes
cảm ơn bác ạ, để em đọc xem
có người bảo em dùng thuật toán quay lui, em chưa biết thuật toán này ạ. Quay lui vói sinh hoán vị của bác trên thì nên dùng các nào hơn ạ?
PP sinh sẽ hay hơn vì đằng nào chả in hết 
lại dễ hiểu.
Ta thấy rằng “54321” (n = 5) là max rồi. Vậy thì hoán vị tiếp theo của “34521” là gì?
Để ý 5 4 3 2 1 là dãy giảm ngặt nên về mặt nào đó, “34521” cũng là max của prefix “34”. Vậy để tăng lên ta chọn suffix.min(c: c > prefix.tail()).
Vậy prefix tiếp theo là “35”. Mà “12345” là min nên min của prefix “35” là “35124”. “124” suffix này rất là quen
Summary
Dãy giảm ngặt là hoán vị lớn nhất.
Với sym[n] > sym[n-1] > … > sym[1], xét trt a>b := sym[n] x sym[n] -> a[L] > b[L] && ∀i \ L < i <= n, a[i] = b[i].
Trong các hoán vị, hoán vị có sym[n] đứng đầu là lớn nhất […] QED.
Tương tự cho hoán vị bé nhất.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?