Chỉnh hợp không lập chập k của n trong C++

Một chỉnh hợp không lặp chập k của n phần tử là một cách sắp xếp có thứ tự gồm k phần tử khác nhau lấy từ n phần tử đã cho (với k < n).
Ví dụ: Có 5 chữ số 1, 2, 3, 4, 5. Hãy lập tất cả các số gồm 2 chữ số khác nhau?
Giải
Nếu bạn làm theo cách thủ công thì cứ ghép các số 1, 2, 3, 4, 5 với điều kiện loại bỏ 2 số giống nhau:
11, 12, 13, 14, 15
21, 22, 23, 24, 25
31, 32, 33, 34, 35
41, 42, 43, 44, 45
51, 52, 53, 54, 55

Để dễ nhớ ta sử dụng công thức sau:

Để liệt kê các chỉnh hợp không lặp chập k của tập S = {1, 2, .. , n} ta có thể đưa về liệt kê các cấu hình a[1..k] ở đây các a[i] ∈ S và khác nhau đôi một.Như vậy hàm chinhhop (i) – xét tất cả các khả năng chọn a[i] – sẽ thử hết các giá trị từ 1 đến n, mà các giá trị này chưa bị các phần tử đứng trước chọn. Muốn xem các giá trị nào chưa được chọn ta sử dụng kỹ thuật dùng mảng đánh dấu:
- - Khởi tạo một mảng c[1..n] mang kiều logic boolean. Ớ đây c[i] cho biết giá trị i có còn tự do hay đã bị chọn rồi. Ban đầu khởi tạo tất cả các phần tử mảng c là TRUE có nghĩa là các phần tử từ 1 đến n đều tự do.
  - Tại bước chọn các giá trị có thể của a[i] ta chỉ xét những giá trị j có c[j] = TRUE có nghĩa là chỉ chọn những giá trị tự do.
  - Trước khi gọi đệ quy tìm a[i+1]: ta đặt giá trị j vừa gán cho a[i] là đã bị chọn có nghĩa là đặt c[j] := FALSE để các hàm chinhhop (i + 1), chinhhop (i + 2)… gọi sau này không chọn phải giá trị j đó nữa
  - Sau khi gọi đệ quy tìm a[i+1]: có nghĩa là sắp tới ta sẽ thử gán một giá trị khác cho a[i] thì ta sẽ đặt giá trị j vừa thử đó thành tự do (c[j] := TRUE), bởi khi a[i ] đã nhận một giá trị khác rồi thì các phần tử đứng sau: a[i+1], a[i+2] … hoàn toàn có thế nhận lại giá trị j đó. Điều này hoàn toàn hợp lý trong phép xây dựng chỉnh hợp không lặp: a[1] có n cách chọn, a[2] có n – 1 cách chọn, …Lưu ý rằng khi hàm chinhhop (i) có i = k thì ta không cần phải đánh dấu gì cả vì tiếp theo chỉ có in kết quả chứ không cần phải chọn thêm phần tử nào nữa.
  - Code C++:
```
 
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define MAX 100
#define TRUE 1
#define FALSE 0

int n,k,j, sum = 0; // sum để đánh số thứ tự của tổ hợp
int a[MAX], c[MAX];

void Docfile()
{
    //Đọc dữ liệu từ file input.inp
    ifstream file;
    file.open("input.inp");
    file>>n>>k;
    file.close();
     
     //Khởi tạo giá trị cho c[], gán tất cả các giá trị là TRUE, chưa chọn
     for( j>0;j <= n;j++)
     c[j] = TRUE;
}

//Hàm in ra kết quả, ghi dữ liệu lên file 
void xuatMang() //in cấu hình tìm được
{
     ofstream file;
     file.open("input.out",ios::app);
     file<<"\nChỉnh hợp không lặp chập k thứ " << ++sum <<" : "<<endl;
     for( int i=1;i<=k;i++)
     file<<" "<<a[i];
     file<<endl;
     file.close();
}

void chinhhop( int i)


{
     for( int j =1;j<=n;j++)
     {
          if(c[j]) // chỉ xét những giá trị j còn tự do
          {
                    a[i] = j;
                    if( i == k)xuatMang(); // nếu đã chọn được đến ak thì in kết quả 
                    {
                        c[j] = FALSE; //đánh dấu j đã chọn
                        chinhhop(i+1);//xét các giá trị còn tự do gán cho a[i+1]
                        c[j] =  TRUE; // Bỏ đánh dấu j tự do, bởi sắp tới sẽ thử một cách chọn khác của a[i]
                    }
          }
     }
}

int main()
{
      Docfile();
      chinhhop(1); // thử các cách chọn giá trị của a[1];
      
}
```

Số lượt xem: 3.951

Trả lời Hủy