Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự


[Kinh nghiệm]Sinh các hoán vị và tổ hợp5511


Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Sinh các hoán vị và tổ hợp
    1. Sinh các hoán vị:
    Mọi tập n phần tử đề có thể tương ứng với tập {1, 2,..., n}
    Chúng ta có thể liệt kê các hoán vị của một tập bất kỳ gồm n phần tử bằng cách sinh ra các hoán vị của tập n số nguyên dương nhỏ nhất, sau đó thay thế các số nguyên này bằng các phần tử tương ứng của chúng. Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập này. Chúng ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập {1, 2...n} theo thứ tự từ điển.
    Khi đó hoán vị a1, a2, ..., an được gọi là đi trước (nhỏ hơn) hoán vị b1, b2, ..., bn nếu với k nào đó ( 1 ≤ k ≤ n ) , a1 = b1 , a2 = b2 ,... ak-1 = bk-1 ak < bk . Nói cách khác, một hoán vị của tập n số nguyên dương đầu tiên được gọi là đi trước (theo thứ tự từ điển) một hoán vị khác nếu con số của hoán vị đầu tại vị trí đầu tiên mà 2 hoán vị khác nhau, nhỏ hơn con số thuộc hoán vị thứ 2 cũng ở vị trí đó.
    Ví dụ 1:
    Hoán vị 23415 của tập {1, 2, 3, 4, 5} là đi trước hoán vị 23514, vì những hoán vị này trùng nhau ở 2 vị trí đầu tiên, nhưng số 4 ở vị trí thứ 3 của hoán vị đầu nhỏ hơn số 5 cũng ở vị trí 3 của hoán vị sau. Tương tự hoán vị 41532 là đi trước 52143.

    Thuật toán sinh các 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ị liên tiếp này.

    Đầu tiên ta giả sử an-1 < an. Rõ ràng nếu đổi chỗ an-1an cho nhau thì ta nhận được hoán vị mới (đi sau) hay lớn hơn hoán vị đã cho, và không thể có hoán vị nào khác lớn hơn hoán vị xuất phát mà lại bé hơn hoán vị nhận được bằng việc đổi chỗ an-1an cho nhau. Ví dụ, hoán vị liền tiếp sau hoán vị 234156 là hoán vị 234165. Nếu an-1 > an thì không thể nhận được hoán vị lớn hơn bằng cách đổi chỗ 2 phần tử này trong hoán vị.

    Bây giờ ta xem xét 3 số. Nếu an-2 < an-1 thì có thể sắp xếp lại 3 số cuối cùng để có thể nhận được một hoán vị mới liền sau hoán vị xuất phát. Đặt số nhỏ hơn trong 2 số an-1an vào vị trí n-2 sau đó đặt số nguyên còn lại và số an-2 vào 2 vị trí cuối cùng theo thứ tự tăng dần. Ví dụ hoán vị liền sau hoán vị 234165 là 234516.

    Nếu an-2 > an-1 (và trước đó đã an-1 > an) khi đó không thể nhận được hoán vị lớn hơn bằng cách đổi chỗ 3 số hạng cuối cùng của hoán vị. Dựa trên những nhận xét này ta có thể mô tả phương pháp tổng quát tạo hoán vị liền sau (theo thứ tự từ điển) của hoán vị cho trước a1, a2, ..., an như sau:

    Trước tiên tìm các số nguyên ajaj+1 sao cho aj < aj+1aj+1> aj+2>...>an tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số trước nhỏ hơn số sau. Sau đó , để nhận được hoán vị liền sau, Khách viếng thăm đặt vào vị trí thứ j số nguyên dương nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2..., an vào các vị trí j + 1, ..., n. Dễ thấy không có hoán vị nào lớn hơn hoán vị xuất phát và nhỏ hơn hoán vị vừa tạo ra.

    Ví dụ 2.
    Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 362541:

    Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau là a3 = 2 và a4 =5. Số nhỏ nhất trong các số bên phải của số 2 mà lại lớn hơn 2 là số 4. Đặt số 4 vào vị trí 3. Sau đó đặt các số 2, 5, 1 theo thứ tự tăng dần vào 3 vị trí còn lại. Ta được hoán vị liền sau hoán vị đã cho là 364125.

    Để sinh ra n! hoán vị các số 1, 2, ..., n chúng ta sẽ bắt đầu bằng hoán vị nhỏ nhất theo thứ tự từ điển , tức là 12,...n và áp dụng liên tiếp (n! -1) lần thủ tục đã mô tả ở trên. Bằng cách đó Khách viếng thăm nhận được tất cả các hoán vị của n số nguyên.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Ví dụ 3.
    Hãy tạo ra các hoán vị của các số nguyên 1, 2, 3 theo thứ tự từ điển:

    Chúng ta bắt đầu bằng hoán vị 123. Bằng cách đổi chỗ 3 và 2 ta nhận được hoán vị tiếp theo 132. Tiếp nữa vì 3 > 2 và 1 < 3 nên phải xét cả 3 số trong nhóm hoán vị này. Đặt số nhỏ nhất trong 2 số 3 và 2 vào vị trí thứ nhất, sau đó là 2 số 1 và 3 vào vị trí thứ 2 và thứ 3 theo thứ tự tăng dần, tức là ta có 213. Đổi chỗ 1 và 3 cho nhau vì 1 < 3 được 231. Vì 2 < 3 nên được đặt 3 vào vị trí đầu tiên và sau đó là 1 và 2, tức 312 . Cuối cùng đổi chỗ 1 với 2 ta nhận được hoán vị lớn nhất là 321.

    Thuật toán sau đây biểu thị thủ tục tìm hoán vị liền sau, theo thứ tự từ điển , một hoán vị cho trước khác hoán vị lớn nhất n, n-1,..., 2, 1.
    Thuật toán sinh hoán vị liền sau, theo thứ tự từ điển, từ một hoán vị cho trước:

    Proc Hoán_vị_liền_sau (a1a2 ... an): Hoán vị của {1, 2,..., n} khác n, n-1,...2, 1
    j := n - 1
    while aj > aj+1
    j := j - 1; {j là chỉ số lớn nhất mà aj < aj+1 }
    k := n
    while aj > ak
              k := k -1 {ak là số nguyên nhỏ nhất trong các số lớn hơn aj và nằm bên phải aj}
              Đổi_chỗ (aj, ak)
              r := n;
              s := j + 1
    while r > s {Xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần}
              Đổi_chỗ (ar, as)
              r := r - 1; s := s + 1;
    end.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Sinh các tổ hợp
    Làm thế nào để tạo ra tất cả các tổ hợp các phần tử của một tập hữu hạn ? Vì tổ hợp chính là một tập con , nên ta có thể dùng phép tương ứng một - một giữa các tập con của {a1, a2, ..., an} và xâu nhị phân độ dài n.

    Nhớ lại là 1 xâu nhị phân ứng với 1 tập con , tại vị trí k, sẽ có số 1 hoặc số 0 tùy theo phần tử ak thuộc vòa tập con đó hay không. Nếu có thể liệt kê tất cả các xâu nhị phân ra được thì ta sẽ nhận được tất cả các tập con.

    Mặt khác ta thấy một xâu nhị phân độ dài n cũng là triển khai nhị phân của một số nguyên nằm giữa 0 và 2n - 1 . Khi đó 2nxâu nhị phân có thể liệt kê theo thứ tự tăng dần của số nguyên trong biểu diễn nhị phân của chúng. Chúng ta sẽ bắt đầu từ xâu nhị phân bé nhất 00..00 (n số 0) . Mỗi bước để tìm xâu liền sau ta tìm vị trí đầu tiên tính từ phải qua trái mà ở đó là số 0. Sau đó thay tất cả số 1 ở bên phải số này = 0 và đặt số 1 vào chính vị trí này.

    Hãy tìm xâu nhị phân liền sau của 10001 00111:

    Bit đầu tiên từ bên phải sang = 0 là bit thứ 4. Ta thay đổi nó bằng số 1 và 3 bit bên phải 1, sẽ thay bằng số 0. Từ đó ta nhận được dãy nhị phân liền sau là 1000101000.

    Thuật toán sinh xâu nhị phân liền sau:

    Proc Xâu_Nhị_Phân_Liền_Sau (a1, a2, ..., an: Xâu nhị phân khác 11...11)
    i := 0
    while ai = 1 do
              ai = 0
              i := i + 1
    ai = 1
    Tiếp theo ta sẽ trình bày thuật toán tạo các tổ hợp chập r từ n phần tử {1, 2...n}. Mỗi tổ hợp chập r có thể biểu diễn bằng một xâu tăng. Khi đó có thể kiệt kê các tổ hợp theo thứ tự từ điển. Có thể xây dựng tổ hợp liền sau tổ hợp a1, a2, ..., an bằng cách sau. Trước hết, tìm phần tử đầu tiên ai trong dãy đã cho kể từ phải qua trái sao cho với j = i + 1 , i + 2,..., r. Nào Khách viếng thăm hãy tự chứng minh thủ tục trên sinh ra tổ hợp liền sau. Còn bây giờ ta xét ví dụ minh họa thủ tục này nhé.
    Tìm tổ hợp chập 4 từ tập (1, 2, 3, 4, 5, 6) đi liền sau tổ hợp (1, 2, 5, 6):

    Lùi từ phải qua trái ta thấy a2 = 2 là phần tử đầu tiên của tổ hợp đã cho thỏa mãn điều kiện a ≠ 6 - 4 + i. Để nhận được tổ hợp tiếp sau, ta tăng ai lên 1 đơn vị, tức a2 = 3, sau đó đặt a3 = 3 + 1 = 4, và a4 = 3 + 2 = 5. Vậy tổ hợp liền sau tổ hợp đã cho là {1, 3, 4, 5}

    Thuật toán
    Sinh tổ hợp chập R liền sau theo thứ tự từ điển:

    Proc Tổ_hợp_liền_sau (a1 a2, ... ar) : tập con thực sự của tập {1, 2,...n} không bằng { n-r+1,..., n} với a1< a2 < ...< ar)
    i := r
    while ai = n - r + i
              i := i - 1
              ai = ai + 1
    for j := i + 1 to r
              aj = ai + j - i


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    hienha


    Chuyên viên
    Chuyên viên
    Admin đã viết:Ví dụ 3.
    Hãy tạo ra các hoán vị của các số nguyên 1, 2, 3 theo thứ tự từ điển:

    Chúng ta bắt đầu bằng hoán vị 123. Bằng cách đổi chỗ 3 và 2 ta nhận được hoán vị tiếp theo 132. Tiếp nữa vì 3 > 2 và 1 < 3 nên phải xét cả 3 số trong nhóm hoán vị này. Đặt số nhỏ nhất trong 2 số 3 và 2 vào vị trí thứ nhất, sau đó là 2 số 1 và 3 vào vị trí thứ 2 và thứ 3 theo thứ tự tăng dần, tức là ta có 213. Đổi chỗ 1 và 3 cho nhau vì 1 < 3 được 231. Vì 2 < 3 nên được đặt 3 vào vị trí đầu tiên và sau đó là 1 và 2, tức 312 . Cuối cùng đổi chỗ 1 với 2 ta nhận được hoán vị lớn nhất là 321.

    Thuật toán sau đây biểu thị thủ tục tìm hoán vị liền sau, theo thứ tự từ điển , một hoán vị cho trước khác hoán vị lớn nhất n, n-1,..., 2, 1.
    Thuật toán sinh hoán vị liền sau, theo thứ tự từ điển, từ một hoán vị cho trước:

    Proc Hoán_vị_liền_sau (a1a2 ... an): Hoán vị của {1, 2,..., n} khác n, n-1,...2, 1
    j := n - 1
    while aj > aj+1
              j := j - 1; {j là chỉ số lớn nhất mà aj < aj+1 }
    k := n
    while aj > ak
    k := k -1 {ak là số nguyên nhỏ nhất trong các số lớn hơn aj và nằm bên phải aj}
    Đổi_chỗ (aj, ak)
    r := n;
    s := j + 1

    while r > s {Xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần}
    Đổi_chỗ (ar, as)
    r := r - 1; s := s + 1;
    end.

    đ/c Admin cần chú ý những câu lệnh trong và ngoài vòng lặp nhé. Những chỗ tôi đánh dấu đỏ ý.


    ================

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | To have a blog