Sinh các hoán vị và tổ hợp

Sinh các hoán vị và tổ hợp

1)      Sinh các hoán vị:

Mọi tập hợp có n phần tử đều có đánh số các phần tử theo chỉ số   k = 1,2,3,..,n.

Thí dụ:

Nếu một tập hợp có n phần tử thì ta có thể ký hiệu các phần tử này là s1,s2,s3,…

Như vậy có sự tương quann 1-1 giữa tập hợp S với tập hợp số nguyên dương nhỏ nhất {1,2,3,…,n}

Như vậy việc liệt kê các hoán vị của S cũng tương đương với việc liệt kê tất cả các hoán vị của 1,2,…,n

Có nhiều thuật toán đã được phát triển để sinh n! hoán vị. Sau đây chúng ta sẽ mô tả một trong những phương pháp đó là phương pháp liệt kê thứ tự từ điển.

Hoán vị < a1,a2,a3,…,an> được gọi là đứng trước hoán vị <b1,b2,…,bn> nếu với k nào đó ( 1<=k<=n),  a1=b1, a2 = b2,…., a(k-1) = b(k-1) và ak< bk, tức là xâu n ký tự a1, a2,…,an nhỏ hơn xâu b1,b2,….,bn.

Nói một cách khác nếu đi từ trái qua phải, tức là cho i đi từ 1 đến n thì tại vị trí đầu tiên mà hai hoán vị khác nhau thì ak < bk.

Nếu a1a2….an biểu diễn số a và b1b2…bn biểu diễn số b thì điều này cũng có nghĩa a<b

Ví dụ: ta có tập {1,2,3,4,5} thì hoán vị 23415 là hoán vị đi trước của hoán vị 23514

Thuật toán sinh hoán vị của tập {1,2,3,…,n} dựa trên thủ tục xây dựng hoán vị kế tiếp, theo thứ tự từ điển, của hoán vị cho trước a1,a2,…,an.

Bây giờ chúng ta sẽ chỉ rõ cách xây dựng hoán vị này. Trở lại ví dụ cụ thể trên, câu hỏi đặt ra là hoán vị đi liền sau hoán vị  hoán vị 12345

Ta có thể thấy ngay đó là hoán vị 12354

Hoán vị liền sau của 12354 la 12435 như vậy ta sẽ đổi vị trí của 3 và 4, sau đó đổi vị trí của 4 và 5.

Bây giờ ta sẽ trình bày cách xây dựng hoán vị liền kề  này một cách tổng quát như sau:

Giải thuật:

void Next_Permutation( int a[] , int n)
{

       tìm vị trí đầu tiên từ phải sang trái mà a[i] < a[i+1];

      if ( tìm được vị  tri)

     {

             tìm vị trí  a[k] đầu tiên từ phải qua trái mà a[i] < a[k];

             // k là vị trí đầu tiên

             Đổi vị trí của a[i] và a[k];

             Lật ngược dãy a[i+1],a[i+2],…,a[n];

              Next_Permutation( a[],n);

     } else ( kết thúc quá trình ) ;

}

              

#include 
using namespace std;

int n,a[100];
void Init()
{
     cout<<"Nhap n =";cin>>n;
     for( int i =1;i<=n;i++)
     a[i] = 0;
}

void View()
{
     cout<< endl;
     for( int i=1;i<=n;i++)
     cout<<" " <0&&a[i]) 
     {
                      a[i] =0;
                      i--;
     }
     if(i>0)
     {
            a[i] = 1;
            Next_Bit_String();
     }
     else return;
}

int main()
{
    Init();
    Next_Bit_String();
    cout<< endl;
    system("pause");
    return 0;
}

            
     
     

2)      Sinh các tổ hợp:

Tạo ra tất cả các tổ hợp của một tập hợp:

Vì mỗi tổ hợp là một tập hợp con, do đó việc liệt kê tất cả các tổ hợp  của một tập hợp tương đương với việc liệt kê tất cả các tập hợp con  của một tập hợp.

Giả sử tập hợp S có n phần tử và được đánh số {s1,s2.s3,…, sn}.

Như chúng ta đã biết, có sự tương ứng một – một giữa các tập con của S với xâu nhị phân có độ dài n.

Việc liệt kê tất cả các tập con của tập S tương đương với việc liệt kê tất cả xâu nhị phân độ dài n.

(chèn code vào đây)

Tạo ra tất cả các tổ hợp chập k của một tập hợp.

Giả sử tập S có n phần tử và được ký hiệu là s1,s2,…,sn.

Như vậy có một sự tương ứng một - một giữa tập S với tập số nguyên dương nhỏ nhất [1,2,…,n].

Như thế tổ hợp chập k của tập S sẽ tương ứng với tổ hợp chập k từ n phần tử [1,2,3,…,n]

Vì thứ tự trong một tổ hợp không quan trọng nên ta quy ước thứ tự sắp xếp trong 1 tổ hợp tăng dần.

Có nhiều thuật toán phát triển để sinh tổ hợp chập k. Chúng ta sẽ mô tả một trong những phương pháp đó là phương pháp liệt kê theo thứ tự từ điển.

Tổ hợp <a1,a2,….,an> được gọi là  đứng trước tổ hợp <b1,b2,…,bn> nếu với i nào đó (1<=i<=k), a1=b1,a2=b2,…,a(i-1) = b(i-1) và ai<bi, tức là xâu k ký tự a1a2…ak nhỏ hơn xâu b1b2…bk.

Nói một cách khác, nếu đi từ trái qua phải, tức là cho  i đi từ 1 đến k thì tại vị trí j đầu tiên mà 2 hoán vị khác nhau thì aj < bj

Ví dụ:

Tổ hợp chập 4 ( k = 4) của 1,2,4,5 của tập {1,2,3,4.5} đi trước tổ hợp 1,2,4,6

Thuật toán sinh các tổ hợp chập k của tập {1,2,3,…,n } dựa trên thủ tục xây dựng tổ hợp kế tiếp, theo thứ tự từ điển, của tổ hợp cho trước a1,a2,…,ak.

Trong ví dụ trên ta thấy tổ hợp xuất phát là 1,2,3,4 và tổ hợp cuối cùng là 3,4,5,6.

Trong trường hợp tổng quát, dãy tổ hợp chập k của n phần tử bắt đầu bằng tổ hợp 1,2,3,…,k và kết thúc bằng tổ hợp  n-k +1, n-k +2,…,n.

Do dãy các phần tử sắp xếp tăng dần, nên ta có ai <= n-k+i.

Các phần tử ai = n-k +i  đạt giá trị Mã, không thể tăng được nữa.

Giải thuật:

void ToHopKe ( int a[], int n, int k)

{

      Tìm vị trí đầu tiên từ phải qua trái ( bắt đầu từ vị trí k) mà giá trị của phần tử đó vẫn có thể tăng

                    ( ai < = n-k +i);

       if ( tìm thấy)

       {

               Tăng giá trị của phần tử đó lên 1  (ai = ai +1) ;

               Gán giá trị sao cho ( ai,…,ak) tạo thành dãy tăng dần với độ lệch là 1;

     } else ( kết thúc quá trình sinh tổ hợp);

}

                 

     

           

      

                                                            

//Sinh to hop chap k
#include
using namespace std;

int n,k,a[100],dem =0;
void Init()
{
  cout<<"So phan tu cua tap hop : "; cin>>n;
  cout<<"\nSo phan tu cua to hop : ";cin>>k;
  for(int i=1;i<=n;i++)
  a[i] = i;
}   

void View()
{
     cout<<"To hop  thu: "  << ++dem << " la: "; 
     for( int i =1;i<=k;i++)
     cout<<" "<< a[i];
     cout<< endl;
}

void ToHopKe()
{
     View();
     int i =k;
     while( a[i]>= (n-k+i))i--;
     if( i>0)
     {
        a[i] +=1;
        for(int j =i+1;j<=k;j++) a[j] = a[i] + j-i;
        ToHopKe();
     }
     else return;
}
     
int main()
{
    Init();
    ToHopKe();
    system("pause");
    return 0;
}