[Lập trình newbie] Mỗi ngày một bài toán (số 4)

[09520281]

Hi all !, Trước tiên rất vui khi ba bạn Cao Văn Nhàn, quoctinvn , Lê Võ Thanh Hồng,......
đã có những tranh luận sôi nổi giúp cho bài toán trở nên dễ hiểu hơn cho các bạn newbie khác. Hi vọng các bạn sẽ tiếp tục với bài toán khá dễ dưới đây :shy:.
Bài toán: Hoán vị (QBHV)
bài này nhằm cho các bạn nhớ lại những xử lý cơ bản về chuỗi là chính.
Đề bài:

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

Input

Gồm 1 dòng duy nhất chứa xâu S

Output

Dò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

Example
Input:
ABAB
Output:
6
AABB
ABAB
ABBA
BAAB
BABA
BBAA
Từ từ đừng làm các em sợ nha hi :stick:

[10520184]

kinh thật.hic

[10520355]

Bài này mình có 2 cách:
1. Dùng đệ quy, sinh ra tất cả các hoán vị, lưu lại và đếm các hoán vị không trùng nhau. Vì n <= 9 nên có tối đa 9! = 362880 hoán vị. Để đếm các hoán vị không trùng nhau, nếu dùng tìm kiếm tuyến tính có thể sẽ bị quá thời gian (lỗi Time limit exceeded). Do đó, có thể sắp xếp lại rồi dùng tìm kiếm nhị phân (binary search).
2. Trong thư viện algorithm (#include <algorithm> và using namespace std; ) có hàm next_permutation() tính ra hoán vị tiếp theo của 1 dãy cho trước. Mình dùng hàm này để tính và in ra các hoán vị. (Cách này ngắn gọn hơn cách trên)

[quoctinvn]

Giới hạn bài này thì có thể dùng phương pháp duyệt, tuy nhiên không cần phải đệ quy sinh hoán vị rồi đếm các hoán vị không trùng nhau như anh Nhàn :haha: cách em làm :

• Sort lại xâu ban đầu, gọi là xâu st
  Chừng nào xâu st chưa là xâu lớn nhất theo thứ tự từ điển
  Tìm từ cuối về đầu 2 vị trí i và j đầu tiên sao cho st[i] > st[j]; i>j.
  Swap st[i] và st[j]. Sort lại xâu con st từ vị trí j+1 đến cuối xâu.
  Cứ mỗi lần tìm được 1 cặp (i,j) như vậy ta được 1 xâu hoán vị của xâu ban đầu, lưu kết quả vào mảng kq theo thứ tự, đó là thứ tự từ điển của xâu ban đầu.

Với n=9 thì thuật này chấp nhận được, tuy nhiên với n lớn hơn thì có thể cải tiến = quicksort và phương pháp tìm nhị phân để tìm cặp (i,j) thỏa.

[10520355]

Em có thể nói rõ hơn cách cải tiến được không?

[11520377]

code 1 bài cho zui )

#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <string.h>
using namespace std;
//--------------
int count=0;
int n,Stop;
char P[10];
//--------------
void Swap(char &a, char &b)
{
    char tg = a;
    a = b;
    b = tg;
}
//---------------
void sapxep(char a[])
{
    for(int i = 0 ; i < n-1; i++)
        for(int j = i + 1; j < n; j++)
        {
            if(a[i]>a[j])
                Swap(a[i],a[j]);
        }
}
//------------
void Next_Hoanvi()  //Tim hoan vi ke tiep
{
    int j,k,l,r;
    j = n - 2;
    while (j>=0 && P[j]>= P[j+1])    j--;
    if (j == -1)
        Stop = 0;
    else
    {
        k = n - 1;
        while (P[j] >= P[k]) k--;
        Swap(P[j], P[k]);
        l = j + 1;
        r = n - 1;
        while (l < r)
        {
            Swap(P[l], P[r]);
            l++;
            r--;
        }
    }// end else
}
void Hoanvi()
{
    Stop = 1;
    while ( Stop)
    {
        count++;
        cout<<endl<<P;
        Next_Hoanvi();
    }
}

int main()
{
    cin.ignore(0);
    cin.getline(P,10);
    n = strlen(P);
    sapxep(P);
    Hoanvi();
    cout<<endl<<count;
    return 0;
} 

Thuật toán cũng giống bạn quoctinvvn

[quoctinvn]

Em cải tiến bài này như sau :
- Phần sort lần đầu thì cài = quicksort, độ phức tạp giảm từ O(N^2) xuống còn O(NlogN)
- Phần tìm cặp (i,j) : Nhận xét nếu xâu con từ vị trí X đến cuối xâu là một xâu không tăng theo thứ tự từ điển thì không tồn tại cặp (i,j) thỏa s[i] > s[j], i>j. Phương pháp ở đây là cần tìm được vị trí đầu tiên từ trái qua phải mà từ đó về cuối xâu là một xâu không tăng theo thứ tự từ điển. Giả sử vị trí tìm được là X, ta tiếp tục tìm từ 1->X-1 vị trí Y sao cho Y gần X nhất và tồn tại vị trí Z nằm trong đoạn X-> cuối xâu thỏa s[Y] < s[Z] sao cho s[Z] nhỏ nhất. Vị trí Y thì cho chạy từ X-1 về 1, với mỗi Y tìm trong X-> cuối xâu bằng phương pháp tìm nhị phân. Độ phức tạp ở đoạn này giảm từ O(N^2) xuống còn O(NlogN).

Em mới nghĩ thế, chưa code thử

[10520355]

Mình nghĩ cái này sẽ dễ hiểu hơn.
Thuật toán sinh hoán vị kế tiếp của tập n phần tử
2012-07-10_212439.jpg

[10520355]

Sao chưa thấy bài số 5 nhỉ?