01 Jun 2015

[Algorithm] Thuật toán sinh tổ hợp lặp chập k của n phần tử

Posted in Lập trình, Thuật toán By levanninh On June 1, 2015

Tổ hợp lặp là gì ?

Chúng ta cần phân biệt giữa tổ hợp lặp với tổ hợp thông thường (tổ hợp không lặp).

Tổ hợp lặp: Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n . Số các tổ lặp chập k của n được ký hiệu là K(k,n) .

Công thức tính tổ hợp lặp: K(k,n) = C (k, n+k−1)

Với C là kí hiệu của tổ hợp không lặp.

Ví dụ: với k = 3 ; n= 2 : Ta có các tổ hợp lặp sau: (1,1,1) , (1,1,2) , (1,2,2) và (2,2,2).

Thuật toán sinh tổ hợp lặp:

Đầu tiên ta cần biết ý tưởng đề cài đặt một thuật toán sinh là gì. Để cài đặt thành công thuật toán sinh ta cần 2 yếu tố:

Xác định được cấu hình đầu và cấu hình cuối.
Xác định được quy luật để sinh một cấu hình từ cấu hình hiện tại.

Áp dụng trong bài toán này (k =3 và n =2 ) ta sẽ có:

Cấu hình đầu : (1,1,1) và cấu hình cuối (2,2,2)

Quy luật: lần lượt tăng giá trị của các số từ phải qua cho đến khi bằng n. Ví dụ: với cấu hình hiện tại là (1,1,1), tăng số tính từ bên phải ta sẽ có cấu hình tiếp theo là (1,1,2).

Chương trình mẫu bằng C++:

Chương trình mẫu in tất cả tổ hợp lặp chập k của n phần tử viết bằng C++ :

#include <iostream>

using namespace std;

int k , n ;
int a[100000] ;
void printResult() {
    for(int i =1 ; i <=k ; i++) {
        cout<<a[i]<<" " ;
     }
     cout<<endl ;
}
void sinh() {
    // sinh cấu hình đầu tiên
    for(int i =1 ; i <=k ; i++) {
        a[i] =1 ;
    }
    printResult() ;
    // sinh cau hình tiếp theo
     int j = k ;
    while(a[1]<n) {
        if(a[j]==n) {
            j-- ;
        }
        a[j]++ ;
        printResult() ;
    }

}

int main()
{
    cin>>k>>n ;
    if(k<0 || n < 0 ) {
        cout<<"Loi: k,n >0"<<endl ;
    }
    else {
        sinh() ;
    }

    return 0;
}

#include <iostream>

using namespace std;

int k , n ;

int a[100000] ;

void printResult() {

for(int i =1 ; i <=k ; i++) {

cout<<a[i]<<" " ;

}

cout<<endl ;

}

void sinh() {

// sinh cấu hình đầu tiên

for(int i =1 ; i <=k ; i++) {

a[i] =1 ;

}

printResult() ;

// sinh cau hình tiếp theo

int j = k ;

while(a[1]<n) {

if(a[j]==n) {

j-- ;

}

a[j]++ ;

printResult() ;

}

int main()

{

cin>>k>>n ;

if(k<0 || n < 0 ) {

cout<<"Loi: k,n >0"<<endl ;

}

else {

sinh() ;

}

return 0;

}

Chương trình mẫu bằng Java:

Phía dưới là chương trình viết bằng Java. Do mình viết theo hướng đối tượng và đảm bảo “tính đóng gói” của nó nên viết hơi kĩ nhé để sau này có gì kế thừa hay tái sử dụng cho dễ. 🙂

Mô tả chương trình:

Để sử dụng được chương trình, ta cần khởi tạo đối tượng ToHopLap với 2 tham số k và n. Sau đó gọi hàm generate(). Kết quả sinh ra lưu vào danh sách kết quả là ResultList. (Xem cụ thể tại hàm main )

Lưu ý: mỗi phần tử của ResultList mình thiết kế thành kiểu String nhé.

import java.util.ArrayList;
import java.util.Scanner;

public class ToHopLap {

    public int k;
    public int n;
    public ArrayList<String> ResultList; // mảng lưu trữ danh sách kết quả

    public ToHopLap(int k, int n) {
        this.k = k;
        this.n = n;
        ResultList = new ArrayList<>();

    }
      int result[] = new int[1000000] ; // mảng cấu hình

    public void insert() { // chèn một cấu hình vào danh sách kết quả
        String temp = "";
        for (int i = 1; i <= k; i++) {
            temp += result[i] + " ";
        }
        ResultList.add(temp);
    }

    public void generate() {

        // generate cấu hình đầu tiên
        for (int i = 1; i <= k; i++) {
            result[i] = 1 ;
        }

        insert(); // thêm cấu hình vào vào tập kết quả

        // generate cau hình tiếp theo
        int j = k;
        while (result[1] < n) {
            if (result[j]== n) {
                j--;
            }
            result[j]++ ;
            insert(); // thêm cấu hình vào vào tập kết quả
        }

    }

    public static void main(String[] args) {
        int k = 0, n = 0;
        Scanner s = new Scanner(System.in);
        k = s.nextInt();
        n = s.nextInt();

        ToHopLap thl = new ToHopLap(k, n);
        thl.generate();
        // in kết quả
        for (String result : thl.ResultList) {
            System.out.println(result);
        }

    }

}

import java.util.ArrayList;

import java.util.Scanner;

public class ToHopLap {

public int k;

public int n;

public ArrayList<String> ResultList; // mảng lưu trữ danh sách kết quả

public ToHopLap(int k, int n) {

this.k = k;

this.n = n;

ResultList = new ArrayList<>();

}

int result[] = new int[1000000] ; // mảng cấu hình

public void insert() { // chèn một cấu hình vào danh sách kết quả

String temp = "";

for (int i = 1; i <= k; i++) {

temp += result[i] + " ";

}

ResultList.add(temp);

}

public void generate() {

// generate cấu hình đầu tiên

for (int i = 1; i <= k; i++) {

result[i] = 1 ;

}

insert(); // thêm cấu hình vào vào tập kết quả

// generate cau hình tiếp theo

int j = k;

while (result[1] < n) {

if (result[j]== n) {

j--;

}

result[j]++ ;

insert(); // thêm cấu hình vào vào tập kết quả

}

public static void main(String[] args) {

int k = 0, n = 0;

Scanner s = new Scanner(System.in);

k = s.nextInt();

n = s.nextInt();

ToHopLap thl = new ToHopLap(k, n);

thl.generate();

// in kết quả

for (String result : thl.ResultList) {

System.out.println(result);

}

Tung Minh's Blog

[Algorithm] Thuật toán sinh tổ hợp lặp chập k của n phần tử

Tổ hợp lặp là gì ?

Thuật toán sinh tổ hợp lặp:

Chương trình mẫu bằng C++:

Chương trình mẫu bằng Java:

Related

About Author

levanninh

Tổ hợp lặp là gì ?

Thuật toán sinh tổ hợp lặp:

Chương trình mẫu bằng C++:

Chương trình mẫu bằng Java:

Related

About Author

levanninh

Related Posts