( Thuật toán quay lui) Liệt kê các chỉnh hợp không lặp chập k của n

Để liệt kê các chỉnh hợp không lặp chập k của tập S = {1,2,3,.., n} , ta có thể đưa về liệt kê các cấu hình

x[1,..,k] trong đó xi thuộc tập S và khác nhau từng đôi một.

Như vậy thủ tục Attempt(i) sẽ xét hết tất cả các khả năng xi chạy từ 1 -> n mà các phần từ này chưa được phần tử đứng trước chọn.

Muốn biết giá trị nào đó đã được phần tử đứng trước chọn hay chưa ta dùng một mảng đánh giá.

* Khởi tạo một mảng c[1...n] có kiểu logic boolean. Ở đây c[i] cho biết giá trị i còn tự do hay đã được chọn rồi. Ban đầu khởi tạo các phần tử của mảng có giá trị TRUE, nghĩa là các phần tử từ 1-> n đều tự do.


* Tại các bước chọn của x[i] ta chỉ chọn các giá trị mà c[i] = TRUE, tức là còn tự do.

* Trước khi gọi đệ qui x[i+1], đặt giá trị j vừa gán cho x[i] là đã chọn , tức là gán c[j] = FALSE để các giá trị x[i+1],x[i+2],... không chọn j nữa.

*Quá trình này sẽ lặp lại đến khi ta chọn được phần tử x[k], lúc này ta sẽ in ra kết quả.

Thuat toan quay lui liet ke cac chinh hop khong lap chap k
                

program arrangement;

const
InputFile = 'iARRANGEMENT';
OutputFile = 'oARRANGEMENT';
max = 100;

var

x: array[1...max] of Integer;
c: array[1...max] of Boolean;
n,k : Integer;
f: Text;

procedure printResult; {Thu tuc in cau hinh tim duoc}

var

   i : Integer;

begin

   for i:= 1 to k do Write (f,x[i],' ');
   WriteLn(f);
   
end;

procedure Attempt ( i: Integer) {Thu cac cach chon x[i] }

var

   j: Integer;
begin

   for j:= 1 to n do
     
      if c[j] then {Chi xet nhung gia tri con tu do }
        begin
         x[i] := j;
         if i = k then printResult(); {In cau hinh tim duoc}
         begin
          else
           c[j] := FALSE; {Danh dau j da duoc chon }
           Attempt(i+1); {Thu cac cach con x[i+1] }
           c[j] := TRUE; {Bo dau danh chon j boi buoc tiep theo ta se xet gia tri khac cho x[i]}
          end;
         end;
end;

begin

Assign( f,InputFile);Reset(f);
ReaLn(f,n,k);

Assign( f, OutputFile); Rewrite(f);
FillChar(c,SizeOf(c),TRUE); {Tat ca cac so deu chua duoc chon}

Attempt(1); {Tim cac kha nang chon cho x[1]}

Close(f);

end;

//Thuat toan quay lui liet ke cac chinh hop khong lap chap k
#include<iostream>
#include<fstream.h>
#define MAX 100
#define TRUE 1
#define FALSE 0

int n,k, sum = 0; // sum de danh so thu tu cua to hop
int a[MAX], c[MAX];

void Init()
{
     //Nhap du lieu tu file iARRANGEMENT.txt
     ifstream f;
     f.open("iARRANGEMENT.txt");
     f>>n>>k;
     f.close();
     
     //Khoi tao gia tri cho c[], gan tat ca cac gia tri la TRUE, chua chon
     for( int i = n;i>0;--i)
     c[i] = TRUE;
}

//Ham in ra ket qua, ghi du lieu len file 
//duoc thu tuc de quy Attemat(i) goi

void printResult()
{
     ofstream f;
     f.open("oARRANGEMENT.txt",std::ios::app);
     f<<"\nChinh hop chap k thu " << ++sum <<" : "<<std::endl;
     for( int i=1;i<=k;++i)
     f<<" "<<a[i];
     f<<std::endl;
     f.close();
}

void Attempt( int i)
{
     for( int j =1;j<=n;++j)
     {
          if(c[j])
          {
                    a[i] = j;
                    if( i == k)printResult(); // In ra ket qua
                    else
                    {
                        c[j] = FALSE;
                        Attempt(i+1);
                        c[j] =  TRUE; // Bo danh dau da chon voi j
                    }
          }
     }
}

main()
{
      Init();
      Attempt(1); // Duyet cac kha nang cua a[1];
      
}