Tìm tất cả các hoán vị của 1 dãy số

[qnhan10a3]

Hihi mình thí cái nỳ cũng hay ai có thuật toán gì hay code mách mình với nhá ! Thaks các đồng chí [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[lavendervip]

Trong quyển DSAP của thầy Lê Minh Hoàng có cái này rồi, trong phương pháp sinh liệt kê các hoán vì. Nhưng code đó của thầy hình như là liệt kê các hoán vị từ 1->n, bạn phải sửa đổi 1 chút đối với dãy số, đặc biệt với dãy các số có thể bằng nhau thì cần nghĩ thêm 1 chút nữa mới được.

[dungthinh225]

Àhh mình tìm thấy rồi _ _! nhìn nhìu chữ ngán thế ko biết hzjzzz _ _!

[nguyenducchung]

Bài này còn 1 cách nữa là dùng đệ qui quay lui.
e lấy lại bài lớp 10 nên có nhiều sơ sót nha a Ginta! (e sẽ sửa lại sau).

uses crt;
var a:array [1..100] of byte;
b:array [1..100] of 0..1;
c:array[1..100] of byte;
d,i,j,n:byte;

procedure nhap;
begin
for i:=1 to n do
begin
write('pt ',i,' : ');readln(c);
end;
end;

procedure xuat;
begin
for i:=1 to n do
write(a:5);
writeln;
inc(d);
end;

procedure find(i:byte);
var j:byte;
begin
if i>n then xuat
else
begin
for j:=1 to n do
if b[j]=1 then
begin
a:=c[j];
b[j]:=0;
find(i+1);
b[j]:=1;
end;
end;
end;

begin
clrscr;
write('nhap n: ');readln(n);
d:=0;
fillchar(b,sizeof(b),1);
nhap;
find(1);
write(d);
readln;
end.

[2edu]

Em kiểm tra lại điều kiện nhé, vì code này chạy sai trong trường hợp dãy có các phần tử bằng nhau. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Còn trường hợp khác nhau anh chưa test được kĩ, nhưng chắc là ok

[lehiep108]

Em kiểm tra lại điều kiện nhé, vì code này chạy sai trong trường hợp dãy có các phần tử bằng nhau. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Còn trường hợp khác nhau anh chưa test được kĩ, nhưng chắc là ok

[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] bởi vậy e mới nói là còn sai sót đó,hjhj

[ndk2303]

Cái code trên bác dùng thuật toàn ntn vậy :-S Trình bày cho e hiễu cái ngả thks !!

[parkhill]

Cái code trên bác dùng thuật toàn ntn vậy :-S Trình bày cho e hiễu cái ngả thks !!

Code của titi làm theo đệ quy quay lui.
Bài này dùng quay lui rồi đánh dấu là được:

procedure bt(k:byte);
var i:byte;
begin
        for i:=1 to n do
             if not dd[i] then
                begin
                        dd[i]:=true;
                        luu[k]:=a[i];
                        if k=n then PRINT
                           else bt(k+1);
                        dd[i]:=false;
                end;
end;

Lời gọi: bt(1)
Mảng dd có tác dụng đánh dấu phần tử thứ i trong mảng có sử dụng trong bộ nghiệm hay chưa, mảng luu để lưu lại phần tử đã chọn.
Thủ tục PRINT để in ra [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
P/s: Không chạy được với n=0. Cần thêm điều kiện.