Cho một xâu S chỉ gồm các chữ cái in hoa, 1 <= độ dài <= 9. Yêu cầu: 1: Có bao nhiêu cách hoán vị các chữ cái của xâu S 2: Liệt kê các hoán vị đó theo thứ tự từ điển InputGồm 1 dòng duy nhất chứa xâu S OutputDòng 1: Ghi số lượng hoán vị tìm được (K) K dòng tiếp theo, mỗi dòng ghi một xâu hoán vị của xâu S theo đúng thứ tự từ điển ExampleInput:
ABAB
Output:
6
AABB
ABAB
ABBA
BAAB
BABA
BBAA Solution: Xây dựng mảng a[] để chứa số lượng các chữ cái xuất hiện trong xâu s.Sau đó dùng đệ quy quay lui để duyệt ( duyệt các chữ cái có a[]>1 ). Về số lượng, nếu duyệt được dãy nào thì đếm dãy đó, thì sẽ bị quá Time, cho nên tính theo công thức : n! / a[i]! với i là các chữ cái khác nhau trong s. Note: Cần sử dụng printf thay cho cout , nếu không sẽ bị quá Time Code tham khảo: include<iostream>
include<string>
include<cstdio>
include<cstdlib>
include<algorithm>
include<cmath>
include<climits>
include<vector>
include<stack>
include<queue>
include<deque>
include <time.h>using namespace std;
string s;
int n;
int a[100];
int gt[]={1,1,2,6,24,120,720,5040,40320,362880};
void Init()
{
cin>>s;
n=s.length();
for(int i=0;i<n;i++)
a[s[i]];
}
void BackTrack(int k)
{
for(int i='A';i<='Z';i)
if(a[i]>0)
{
s[k]=i;
a[i]--;
if(k==n-1) printf("%s\n",s.c_str());
else BackTrack(k+1);
a[i];
}
}
void Solve()
{
int res=gt[n];
for(int i='A';i<='Z';i)
{
if(a[i]>1) res/=gt[a[i]];
}
cout<<res<<endl;
BackTrack(0);
}
int main()
{
Init();
Solve();
}  - *
- HOÁN VỊ: Cho một tập A = {1,2,3,4,5}. Mỗi một số được ghép từ tất cả phần tử gọi là một Hoán Vị.
- Ví dụ với tập A. 25431 là 1 hoán vị, 14325 cũng là 1 hoán vị
- Tổng cộng tập A có 5! = 120 hoán vị. Tương đương có 120 số có 5 chữ số
- Giữa 2 hoán vị bất kỳ. Thì có số phần tử bằng nhau, chỉ có cách sắp xếp khác nhau.
- Ký hiệu Pn = n!
- CHỈNH HỢP: Cho một tập A = {1,2,3,4,5}. Ta sẽ xem có bao nhiêu số có 3 chữ số được tạo từ những phần tử trong tập A. Gọi số đó là ABC:
- Số A ta có 5 lựa chọn từ 1-5. Số B ta có 4 lựa chọn vì A chọn mất 1 số. Tương tự C còn có 3 lựa chọn.
- Vậy ABC sẽ có 5*4*3 = 60 chữ số có 3 chữ số được khi ghép các phần tử trong A vào với nhau.
- Đó gọi là Chỉnh Hợp. Chính xác hơn theo ví dụ trên thì đó là chỉnh hợp chập 3 của 5.
- Ký hiệu Akn = n! / (n-k)!
- TỔ HỢP: Tổ hợp chập k của n. Ký hiệu là Ckn là phép chia của tổng số chỉnh hợp chập k của n cho số hoán vị k ( hay còn gọi là k giai thừa).
- * Công thức Ckn = Akn / k!
- Tổng quát về tổ hợp. Khi bạn có tập A = {1,2,3,4,5}. Bạn muốn tạo một tập con B từ tập A nhưng mà chỉ cho B lấy 3 phần tử từ A thôi. Vậy câu hỏi đặt ra là B sẽ bao nhiêu trường hợp?
- B có thể là {1,2,3} hoặc {1,3,4} hoặc {1,4,5}….
- Thực chất một B có thể tạo được 6 chữ số khác nhau.
- Ví dụ B = {1,2,3} => 123, 132, 213, 231, 321, 312.
- Mỗi một tập con B sẽ tạo được 6 số khác nhau
- Vậy thì ta hẳn đã đoán được 1 chỉnh hợp chập 3 của 5 sẽ lớn hơn gấp 6 lần so với tổ hợp chập 3 của 5.
- Và con số 6 lần đó chính là bằng 3!
- Vậy Tổ hợp chập 3 của 5 sẽ bằng 60/3! = 10.
- Công thức Ckn = n! / ((n-k)! * k!)
- Ví dụ: Một lớp có 12 nam và 8 nữ, cử ngẫu nhiên đoàn đại biểu gồm 5 người
- A. Tính xem có bao nhiêu cách chọn.
- B. Tính xem có bao nhiêu cách chọn 3 nam và 2 nữ
- Giải:
- A. Vì chọn ngẫu nhiên 5 người trong 20 người, không phân biệt nam nữ cũng như sắp xếp nên nó sẽ là tổ hợp chập 5 của 20.
- C520 = 20! / ((20-5)! * 5!) = 15504 cách lựa chọn
- B. Chúng ta cần chọn ngẫu nhiên 3 bạn nam và ghép với 2 bạn nữ do đó nó là một tổ hợp 3 nam bất kỳ ghép với một tổ hợp 2 nữ bất kỳ.
- Ta có C312 * C28 = [12! / ((12-3)! * 3!)] * [8! / ((8 -2)! * 2!)] = 6160 cách lựa chọn
Điều hướng bài viết | 
