Chỉnh hợp lập chập k của n phần tử trong C++

• • Nhắc lại một số kiến thức đại số tổ hợp:
  • Chỉnh hợp lặp:
  • Cho một tập X gồm n(n ∈ N*) phần tử. Một dãy có độ dài m(m ∈ N*) các phần tử của X, trong đó mỗi phần tử có thể lặp lại nhiều lần, sắp xếp theo một thứ tự nhất định gọi là một chỉnh hợp lặp chập m của n phần tử.
    
  • Bài tập vận dụng: Ta cho tập hợp X gồn n phần tử có n phần tử (1,2,3…n)
  • Ví dụ: n=2, k=3:
    Liệt kê các cấu hình: 111, 112, 121, 122, 211, 212, 221, 222
    Cấu hình đầu: 111
    Cấu hình cuối: 222
    Thuật toán:
  • In ra cấu hình đầu:
  • Xét từ cuối dãy về đầu dãy gặp chữ số nào chưa = n
  • + Gán tất cả các số đằng sau bằng 1
  • 
  • Code C++

 
//Sinh các chỉnh hợp lặp chập k của n phần tử
#include<bits/stdc++.h>
using namespace std;
int n,k,i,vt;
//hàm in xâu 
void display(int *a, int k)
{
	for (i=0;i<k;i++)
	{
		cout<< a[i];
	}
		cout<<endl;
}
//trả về 1 xét xâu tiếp theo
void replace(int *a, int k, int vt)
{
	for (i=vt;i<k;i++)
	{
		a[i]=1;
	}
}
//xây dựng và in xâu tiếp theo
void nextstring(int *a, int n, int k)
{
	i=k-1;
	while (i>0)
	{
		if (a[i]==n) 
		i--;
		if (a[i]<n)
		{
			a[i]++;
			replace(a,k,i+1);
			display(a,k);
			i=k-1;
		}
	}
	
}
int main()
{
	cout<<"Nhập vào n và k: ";
	cin >> n >> k;
//khai báo mảng chứa xâu con
	int *a = new int[n]; //cấp mảng động cho mảng a
//Khởi tạo xâu ban đầu
	for (i=0;i<=k;i++)
	{
		a[i] = 1;
	}
//In xâu con
	display(a,k);
	nextstring(a, n, k);
	return 0;
}