Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 8 trên tổng số 8 kết quả

Đề tài: Liệt kê hoán vị bằng thuật toán Johnson-Steinhaus-Trotter

  1. #1
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    582

    Mặc định Liệt kê hoán vị bằng thuật toán Johnson-Steinhaus-Trotter

    Mã nguồn mình đã gửi tại congdongcviet, ai cần có thể tự tìm. Dưới đây là cơ sở lí thuyết.

    ================================================== ===
    Bài của queensland gửi tại diendantoanhoc.net.
    ================================================== ===
    Chào các bạn, tuần vừa rồi queensland phải giải một bài toán bằng máy tính, tìm được một thuật toán thấy cũng hay hay nên post lên đây cho các bạn xem chơi. Đó là thuật toán Johnson-Steinhaus-Trotter, dùng để liệt kê các hoán vị.

    Liệt kê là một vấn đề rất cơ bản của lập trình. Liệt kê có nghĩa là lần lượt duyệt qua từng phần tử của một tập hợp cho trước sao cho mỗi phần tử được duyệt qua đúng một lần, và in ra giá trị của từng phần tử. Tất nhiên hành động "in ra" có thể thay bằng một hành động nào đó khác trên phần tử, vì thế mỗi thuật toán liệt kê cho một tập hợp sẽ là một cái "khung" cơ bản cho nhiều thuật toán xử lý tập hợp ấy. Thí dụ sau đây liệt kê các số chẵn từ 0 đến 2*N:

    Code:
    for i := 0...N loop
      print(2*i)
    end loop
    (Trong bài này không dùng ngôn ngữ lập trình nào cả. Mọi code đều là pseudo-code.)

    Vì tập hợp các số chẵn rất đơn giản, thuật toán liệt kê trong trường hợp này chỉ là một vòng lặp.

    Bây giờ ta nói đến bài toán chính, là liệt kê các hoán vị. Một hoán vị N phần tử được cho bằng một bảng p[1,...,N], mỗi ô là một số tự nhiên từ 1 đến N, không số nào giống số nào cả. Ví dụ, sau đây là danh sách tất cả các hoán vị 3 phần tử:

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

    Làm thế nào để liệt kê tất cả N! hoán vị N phần tử? Thứ tự các hoán vị trong danh sách là không đáng quan tâm, cốt sao liệt kê được càng nhanh càng tốt, bởi vì với N = 16 chẳng hạn, một máy vi tính mạnh cũng phải làm mất vài ngày.

    Một thuật toán tự nhiên, có thể nói là "ngây thơ", như sau:

    Code:
    recursive procedure LietKeHoanVi (k, p[])
    --- thu tuc nay liet ke moi hoan vi p[1...k]
    begin
    if k >= 2 then
      for c := 1...k loop
        h := p[1];
        for i := 1...k - 1 loop
          p[i] := p[i+1]
        end loop;
        p[k] := h
        LietKeHoanVi(k-1, p)
      end loop
    else --- k = 1
      print(p) --- in ra hoan vi p[1...N]
    end if
    end
    Cách dùng (chẳng hạn N = 3):

    Code:
    p[] = (1, 2, 3)
    LietKeHoanVi (3, p)
    Diễn tả bằng lời: muốn liệt kê hoán vị các số trong mảng p[1...k], k>=2, ta đặt một số vào vị trí "cố định" ở cuối mảng (p[k]) nhờ hoán vị vòng quanh p[1...k] và liệt kê hoán vị phần còn lại (p[1...k-1]).

    Trong thuật toán tự nhiên này, các hoán vị vòng quanh độ dài 2, 3,..., N được sử dụng. Hoán vị vòng quanh độ dài N được dùng N lần, độ dài N-1 dùng (N-1)*N lần, độ dài N-2 dùng (N-2)*(N-1)*N lần, v.v. Bởi vì thời gian thực hiện một hoán vị vòng quanh độ dài N tỷ lệ thuận với N, thuật toán này không hiệu quả lắm.

    Thuật toán Johnson-Steinhaus-Trotter sắp trình bày sau đây là một thuật toán liệt kê hoán vị hiệu quả. Từ một hoán vị sinh một hoán vị mới chỉ cần hoán vị đúng một cặp số, và hơn nữa, đó luôn là 2 số đứng liền kế nhau trong mảng.

    Thuật toán Johnson-Steinhaus-Trotter dựa trên một ý tưởng đơn giản. Hãy xem liệt kê các hoán vị 2 số:

    1 2
    2 1

    Để liệt kê các hoán vị 3 số, đầu tiên ta chép lại danh sách trên, mỗi hàng được chép lặp 3 lần:

    1 2
    1 2
    1 2

    2 1
    2 1
    2 1

    viết thêm số 3 vào cuối hoán vị nhứ nhất, rồi tuần tự "di chuyển" số 3 ra phía đầu hoán vị, ta được 3 hoán vị 3 phần tử:

    1 2 3
    1 3 2
    3 1 2

    giữ số 3 ở vị trí đầu một lần nữa, rồi tuần tự "di chuyển" số 3 về phía cuối hoán vị, ta thu được nốt 3 hoán vị 3 phần tử:

    3 2 1
    2 3 1
    2 1 3

    Tiếp tục tương tự với số 4, ta sẽ thu được 24 hoán vị 4 phần tử:

    1 2 3 4
    1 2 4 3
    1 4 2 3
    4 1 2 3

    4 1 3 2
    1 4 3 2
    1 3 4 2
    1 3 2 4

    3 1 2 4
    3 1 4 2
    3 4 1 2
    4 3 1 2

    4 3 2 1
    3 4 2 1
    3 2 4 1
    3 2 1 4

    2 3 1 4
    2 3 4 1
    2 4 3 1
    4 2 3 1

    4 2 1 3
    2 4 1 3
    2 1 4 3
    2 1 3 4

    Và cứ thế tiếp tục với số 5, 6,..., N. Thuật toán Johnson-Steinhaus-Trotter trình bày theo lối này hẳn là đủ rõ ràng đến mức không cần phải chứng minh rằng nó thực sự liệt kê mọi hoán vị N số, và hơn nữa theo thứ tự sao cho hoán vị thứ i với thứ i+1 chỉ sai khác nhau ở đúng một cặp số đứng liền kế nhau. Thêm vào đó, hoán vị cuối cùng (thứ N!) so với hoán vị đầu tiên (thứ 1) cũng chỉ sai khác nhau ở đúng một cặp số đứng liền kế nhau (cặp nào? câu hỏi này xin nhường cho bạn đọc).


    Số 3 (và 4) trong các liệt kê nói trên gọi là số nguyên lưu động. Khi thực hiện trên máy tính ta không liệt kê hết các hoán vị 2 (và 3) ra trước khi liệt kê các hoán vị 3 (và 4), nghĩa là ta phải làm việc đồng thời với nhiều số nguyên lưu động. Để nhớ vị trí của số nguyên lưu động, ta dùng mảng pi[] là hoán vị ngược của p[] theo nghĩa pi[p[x]] = x (với mọi x) và p[pi[k]] = k (với mọi k). Ta còn dùng mảng d[] để ghi nhớ chiều di chuyển của số nguyên lưu động, nghĩa là d[k] = +1 hoặc -1 (với mọi k).


    Thuật toán

    Code:
    recursive procedure JohnsonSteinhausTrotter (k, p[], pi[], d[])
    --- k = so nguyen luu dong tuc thoi
    begin
      if k<=N then
        JohnsonSteinhausTrotter (k+1, p, pi, d)
        for c := 1...k-1 loop
            --- doi tri p[x], p[y], trong do x = pi[k], y=x+1 hoac x-1
            x := pi[k]; y := x + d[k];
            j := p[y];
            p[x] := j; pi[j] := x;
            p[y] := k; pi[k] := y;
            JohnsonSteinhausTrotter (k+1, p, pi, d)
        end loop
        d[k] := -d[k]
      else --- tai day k > N
        print(p) --- in ra hoan vi p[1...N]
      end if
    end

    Cách dùng (thí dụ với N=3):

    Code:
    p[1...3] := (1,2,3)
    pi[1...3] := (1,2,3)
    d[1...3] := (-1,-1,-1)
    JohnsonSteinhausTrotter (1, p, pi, d)

    Lịch sử và tư liệu

    Thuật toán này mang tên Johnson, Steinhaus và Trotter, ba tác giả độc lập với nhau, đã tìm ra và công bố thuật toán trong khoảng thời gian 1959-1963. (Tôi chỉ biết thế thôi, chứ chưa được đọc nguyên tác.) Tuy nhiên, có lẽ họ không phải là những người đầu tiên biết thuật toán này. Sách cổ của nhà thờ Anh quốc từ thế kỷ 16 còn ghi bài toán đánh chuông nhà thờ: bộ chuông có N chiếc chuông kích thước và âm thanh khác nhau; mỗi hồi chuông đánh cả N chiếc mỗi chiếc một lần; cần xây dựng trình tự đánh chuông sao cho tiếng chuông nghe êm tai, nghĩa là không có hồi chuông nào nào giống hồi nào và tiếng chuông ở hai hồi liên tiếp nhau sai khác nhau ít nhất. Sách cổ không ghi lời giải tổng quát nhưng có ghi vài trình tự đánh chuông giống với liệt kê hoán vị Johnson-Steinhaus-Trotter cho N <=6.

    Pseudo-code cho procedure JohnsonSteinhausTrotter dịch từ mã nguồn (ngôn ngữ C) của Frank Ruskey, thay đổi một chút không đáng kể. Có thể tiếp cận mã nguồn nguyên bản qua địa chỉ http://www.nist.gov/dads/HTML/johnsonTrotter.html.

    ================================================== ===
    Bài của queensland gửi tại diendantoanhoc.net.
    ================================================== ===

    Đây là một hình minh họa cho tính chất của thuật toán rất đẹp và sinh động: http://members.multimania.nl/permutation/
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi Ada : 17-05-2011 lúc 05:28 AM. Lý do: Thêm hình

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    582

    Thật ra, trong liệt kê hoán vị (permutation enumeration) thì thuật toán J-S-T không phải là thuật toán nhanh nhất. Trong thư viện chuẩn STL của C++ có một thuật toán hỗ trợ liệt kê hoán vị theo thứ tự từ điển (lexicographic order) nhanh hơn J-S-T, tên là thuật toán L. Cơ sở lí thuyết của L có thể tìm thấy trong quyển sách giáo khoa lập trình danh tiếng của Knuth D.: The Art of Computer Programming.

  3. #3
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Thanks bài viết của Ada, đúng là trong làng C Việt có cậu rất thiên về algorithm, Peter rất thích các bài viết của cậu.

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    582

    Cám ơn peterdrew. Thật ra bài trên không phải do mình viết, mình chỉ là người sưu tầm. Nhưng lời khen của bạn cũng làm mình rất phấn khởi và muốn đóng góp nhiều hơn nữa.

  5. #5
    Ngày gia nhập
    11 2010
    Bài viết
    31

    thanks bác nhìu nhé.

  6. #6
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Mặc định Liệt kê hoán vị bằng thuật toán Johnson-Steinhaus-Trotter

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    Thật ra, trong liệt kê hoán vị (permutation enumeration) thì thuật toán J-S-T không phải là thuật toán nhanh nhất. Trong thư viện chuẩn STL của C++ có một thuật toán hỗ trợ liệt kê hoán vị theo thứ tự từ điển (lexicographic order) nhanh hơn J-S-T, tên là thuật toán L. Cơ sở lí thuyết của L có thể tìm thấy trong quyển sách giáo khoa lập trình danh tiếng của Knuth D.: The Art of Computer Programming.
    Không biết Ada có file pdf của cuốn "The Art of Computer Programming" không? Nếu có thì cho tôi 1 cái link nhé. Cám ơn.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  7. #7
    Ngày gia nhập
    12 2008
    Nơi ở
    Hà Nội
    Bài viết
    374

    Trích dẫn Nguyên bản được gửi bởi doicanhden Xem bài viết
    Không biết Ada có file pdf của cuốn "The Art of Computer Programming" không? Nếu có thì cho tôi 1 cái link nhé. Cám ơn.
    Google keyword : The Art of Computer Programming site:4shared.com

    Thử xem

  8. #8
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi luc13aka47 Xem bài viết
    Google keyword : The Art of Computer Programming site:4shared.com

    Thử xem
    Oh, tks, Tôi dùng keyword "The Art of Computer Programming" filetype:pdf nên tìm mãi không ra. Chắc do dung lượng lớn và có nhiều phần.
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

Các đề tài tương tự

  1. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  2. Chuyên thiết kế, cung cấp các thiết bị hệ thống điều khiển tòa nhà BMS của Johnson Controls
    Gửi bởi quangcaosmc trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 05-10-2012, 02:05 PM
  3. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 16-02-2012, 11:07 AM
  4. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 19-05-2010, 02:33 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn