Các Thuật Toán Sinh Kế Tiếp

Omega | om
Doc | Hàm sinh tiếp đến Python Python Cơ phiên bản Python nâng cấp Machine Learning Python với ML ML, Deep Learning bài viết Data Science Data Science Python nội dung bài viết Basic Toán học trong KHMT an ninh & bảo mật TT Tổng hợp Tài liệu tìm hiểu thêm chuyên đề
None

Hàm sinh kế tiếp

Tác giả: trường đoản cú Nghĩa với sự cải tiến và phát triển “siêu to khổng lồ” của mạng Neuron (Neural Network) khi đi phân tích LSTM với model Sequence generation giỏi Sequence lớn sequence trong vấn đề tự sinh câu thoải mái và tự nhiên cho các ứng dụng vấn đáp tự động, tóm tắc văn bản, tự động hóa caption …Liên quan liêu tới các loại “sinhsinh” làm mình hồi ức lại một kiến thức đã học trong toán tránh rạc đó là hàm sinh kế tiếp, nghe tên nó cóchút tương quan với technology sinh câuphải không những bạn rõ ràng như nạm nào, bài viết này mình vẫn nhắc lại hàm sinh tiếp nối để ôn lại lưu niệm thời đại học.

Bạn đang xem: Thuật toán sinh kế tiếp

Giới thiệu:

Trong việc liệt kênhư: + Liệt kệ danh sách những chuỗi nhị phân bao gồm độ dài bởi n. + Liệt kê những cặp tranh tài trong danh sách có 5 nhóm bóng. + Liệt kê các cách đi từ điểm A tới điểm D thế nào cho không qua điểm C (với một thứ thị đang cho). … Mình sẽ nhắc lại 2 nguyên lý trong việc liệt kê: + bề ngoài 1: Các cấu hình không được trùng lặp +Nguyên tắc 2: Không vứt bỏ cấu hình Để giải các bài toán liệt kê tổ hợp này, vào lập trình chúng ta thường cần sử dụng hai biện pháp là con quay lui (đệ quy) với hàm sinh kế tiếp. * cùng với hàm sinh kế tiếp, chúng ta cần thành lập thuật toán tự một cấu hình đang có sinh ra một cấu hình kế tiếp của nó. vậy nên để áp dụng thuật toán sinh kế tiếp, bài toán cần phải xác định: + thông số kỹ thuật đầu tiên và cấu hình cuối thuộc (việc này hay khá đơn giản) + phép tắc sinh hàng kế tiếp: Tuỳ thuộc vào yêu cầu bài toán. Thông thường cấu hình tiếp theo là thông số kỹ thuật thoả mãn và gần kề với thông số kỹ thuật trước nó cùng với các bộ phận có chuyển đổi theo vật dụng tự tự trước ra sau, từ bé dại tới lớn. ( tinh vi hơn ý lắp thêm nhât )Thông qua phần diễn đạt ở trên, thuật toán sinh sau đó được thiết đặt dạng như sau:

""" Input: curr: thông số kỹ thuật hiện tạim : số lượng bộ phận trong thông số kỹ thuật thông tin không gian liên quan
Output:next_curr: thông số kỹ thuật kế tiếp"""def next_generate(, ): if : return # tìm những vị trí phần tử sẽ chuyển đổi trong thông số kỹ thuật hiện tại # biến đổi các bộ phận trong thông số kỹ thuật hiện trên để tạo ra cấu hình kế tiếp return Khá dễ dàng và đơn giản phải không nào

bây giờ chúng ta sẽ thử làm một trong những ví dụ cụ thể để hiểu rõ hơn và có cái nhìn ở tầm mức ứng dụng của sinh tiếp nối nhé

Ứng dụng:

Bài 1Bài Hello world của thuật toán sinh tiếp nối mình sẽ chọn là: Chuỗi nhị phân sau đó có độ dài n.Input: + n: Độ lâu năm của chuỗi nhị phân vd: n = 4 + curr: Chuỗi nhị phân hiện tại vd: curr = <1, 0, 1, 1>Output: + next_curr: Chuỗi nhị phân tiếp đến vd next_curr = <1, 1, 0, 0>Gọi $ b_0b_1...b_n-1 $là một cấu hình | $ b_i $∈ 0, 1 với i ∈ <0, n)Chúng ta thuận lợi xác định:+ Chuỗi đầu tiên:<0, 0, 0 ,0>+ Chuỗi cuối cùng: <1, 1, 1, 1>+ Quy hình thức sinh chúng ta xác định được ngay lập tức là chuỗi sau bởi chuỗi trước thêm 1 theo hệ nhị phân.Đến phía trên các các bạn sẽ thấy rất là đơn giản dễ dàng phải ko nào, một cái code là xongnext_curr = bin(0b1011 + 0b1)Tuy nhiên, mình sẽ phân tích và xây cất thuật toán ở tại mức tổng quát mắng để rất có thể ứng dụng được vào những việc khó rộng nhé:Cộng 1 vào chuỗi nhị phân họ sẽ tuân theo cách: + Đổi bit 0 ngơi nghỉ phía phải cùng thành 1. + Đổi các bit 1 sau nó về 0 ví như có.Phân tích xong, cho lúc cài đặt chương trình nàodef next_generate(curr, n): if set(curr) == 1: # Nếu tổng thể bit 1 thì đang là chuỗi ở đầu cuối return curr i = n - 1 # bước đầu từ vị trí phải cùng while curr: # trong lúc bằng 1 thì đặt lại bởi 0 curr = 0 i -= 1 curr = 1 # Đặt vị trí 0 bên phải cùng về bằng 1 return curr # Trả về chuỗi kế tiếpif __name__ == '__main__': n = 3 curr = <1, 0, 1, 1> next_curr = next_generate(curr=curr, n=n) print(next_curr) # <1, 1, 0, 1>Chuẩn hello world nên không các bạn

Bài 2 Lần này bản thân sẽ chỉ dẫn một ví dụ mang ý nghĩa ứng dụng thực tế hơn chút nhé: lúc xem một trận đá bóng hay lấy ví dụ U23 Châu Á chẳng hạn, một câu hỏi bé dại đặt ra là coi không còn trận này thì mình sẽ coi trận như thế nào nữa (trận tiếp theo trong cùng phiên bản đấu với bảng bao gồm 4 đội) việc khái quát của ví dụ như này là: tra cứu tổ hợp tiếp đến của k phần tử trong tập n phần. Đó là k = 2 với n = 4 yêu cầu không nào. Họ cùng đi phân tích bài xích toán. Input: + n: con số tập không gian phần tử vd: n = 4 + basket: danh sách n phần tử vd: basket = <'Triều Tiên', 'Việt Nam', 'UAE', 'Jordan'> + k: độ nhiều năm của cấu hình. vd: k = 2 + curr: cấu hình hiện tại vd: đang xem curr = <'Triều Tiên', 'Jordan'> Output: + next_curr: thông số kỹ thuật kế tiếp vd: tiếp theo hoàn toàn có thể được xem next_curr = <'Việt Nam', 'UAE'> Theo lý lẽ lập thông số kỹ thuật từ trái sang trọng phải, từ nhỏ dại tới béo thì bọn họ xác định được: + cấu hình đầu tiên: <'Triều Tiên', 'Việt Nam'> + thông số kỹ thuật cuối cùng: < 'UAE', 'Jordan'> + Quy luật sinh tiếp nối là thông số kỹ thuật sau lớn hơn cấu hình trước theo chuỗi máy tự chỉ số đại diện. điện thoại tư vấn tập không gian bài toán S = $ s_0, s_1, ..., s_n-1 $ với a = $ a_0, a_1, ..., a_n-1 $ là chỉ số thay mặt đại diện các phần tử của tập S và tổng hợp c= $ c_0, c_1, ..., c_k-1 $ với $ c_i $∈ a: + $ c_0 + $ c_i(c_i^0c_i^1...c_i^k-1) Trong bài này: s = <'Triều Tiên', 'Việt Nam', 'UAE', 'Jordan'> cùng a = 0 , 1 , 2, 3 các tổ hợp đang là (0,1), (0,2), (0,3), (1,2), (1,3), (2,3) Vậykhi sinh tiếp đến ta tìm kiếm cách thay đổi theo chiều tăng ưu tiên các thành phần từ phía bên yêu cầu cùng Vàthuật toán sinh tổ hợp tiếp nối sẽ thực hiện: + tìm kiếm thành phần vị trí phía bên nên cùng (ci) còn hoàn toàn có thể tăng được $ c_i = n - k + a_i $ + Tăng bộ phận $ c_i $ kia lên 1 $ c_i += 1 $ + thiết lập lại các phần tử phía sau: $ c_j $ (i nếu có theo đồ vật tự tăng nhiều lên 1 bước đầu từ $ c_i $ $ c_j = c_i + j - i $ cài đặt thuật toán kiểm tra nhédef next_generate(n, basket, k, curr): pos = k - 1 while curr == basket: # search vị trí nên cùng hoàn toàn có thể tăng được pos -= 1 if pos là thông số kỹ thuật cuối thuộc return curr for j in range(pos, k): if j == pos: curr = basket) + 1> # tăng phần tử lại vị trí pos lên 1 else: curr = basket) + j - pos> # thiết đặt lại các bộ phận theo sau return currif __name__ == '__main__': n = 4 basket = <'Triều Tiên', 'Việt Nam', 'UAE', 'Jordan'> k = 2 curr = <'Triều Tiên', 'Jordan'> next_curr = next_generate(n=n, basket=basket, k=k, curr=curr) print(next_curr) # <'Việt Nam', 'UAE'> tác dụng đúng rồi bắt buộc không các bạn, mà lại chỉ đúng trong công tác thôi còn thực tiễn thì tuỳ vào sự bố trí của ban tổ chức triển khai nhé

Kết luận

Trong câu hỏi liệt kê, sinh tiếp nối (next generation) và quay lui (backtracking) là phần đông dạng thuật toán giúp chúng ta có thể liệt kê được tất cả các cấu hình.Tuy nhiên khác với backtracking, next generation cho phép chúng ta có thể linh hoạt rộng khi thực hiện như trường hợp chỉ cần một vài cấu hình mong mong chứ chưa phải toàn bộ, mặt mặc dù thường cùng bài bác toán setup với next generation nặng nề hơn là so với trackbacking.Tới đoạn này thì mình đoán các bạn cũng có câu trả lời chocâu hỏi “Next generation có liên quan gì đến câu hỏi sinh câu trường đoản cú động” rồi :))Chào thân ái chúng ta và hẹn gặp gỡ lại

Tham khảo

+ <1> Nguyễn Đức Nghĩa với Nguyễn tô Thành,Toán tách rạc, NXB Giáo dục, 1997.

Các khóa đào tạo qua đoạn clip dành mang lại Hội viên:Python xây dựng C Java C# SQL server PHP HTML5-CSS3-Java
Script
Đăng ký Hội viên
Đăng ký nhận thông báo về những đoạn phim mới nhất

Phương pháp sinh có thể áp dụng nhằm giải vấn đề liệt kê tổ hợp đưa ra nếu như hai đk sau thoả mãn:Có thể khẳng định được một sản phẩm tự bên trên tập các cấu hình tổ hợp bắt buộc liệt kê. Trường đoản cú đó có thể biết đượccấu hình thứ nhất và cấu hình cuối thuộc trong đồ vật tự đó.Xây dựng được thuật toán từ bỏ một cấu hình chưa phải cấu hình cuối, hình thành được thông số kỹ thuật kế tiếp nó.Phương pháp sinh rất có thể mô tả như sau:

Thứ tự trường đoản cú điển

Trên các kiểu dữ liệu đơn giản dễ dàng chuẩn, bạn ta thường nói tới khái niệm máy tự. Ví dụ như trên hình dạng số thì tất cả quan hệ: 1 cùng với mọi a, b, c ϵ STính phổ biến: hay là a ≤ b, hoặc b ≤ a;Tính phản bội xạ: a ≤ a
Tính phản bội đối xứng: nếu như a ≤ b cùng b ≤ a thì đề xuất a = b. Tính bắc cầu: Nếu có a ≤ b và b ≤ c thì a ≤ c.Trong trường hòa hợp a ≤ b cùng a ≠ b, ta dùng cam kết hiệu ", khỏi đề xuất định nghĩa).Ví dụ như dục tình "≤" trên những số nguyên cũng như trên các kiểu vô hướng, liệt kê là quan lại hệ thứ tự toàn phần.

Sponsored Links

Trên những dãy hữu hạn, tín đồ ta cũng khẳng định một quan lại hệ lắp thêm tự:Xét a = (a1, a2, …, an) và b = (b1, b2, …, bn); trên các thành phần của a1, …, an, b1, …, bn đã tất cả quan hệ sản phẩm công nghệ tự "≤". Khi ấy a ≤ b giả dụ như:Hoặc ai = bi với mọi i: 1 ≤ i ≤ n.Hoặc tồn tại một trong những nguyên dương k: 1 ≤ k a1 = b1a2 = b2…ak-1 = bk-1ak = bkak+1 k+1
Trong trường vừa lòng này, ta có thể viết a Thứ trường đoản cú đó gọi là vật dụng tự từ bỏ điển trên các dãy độ dài n.Khi độ nhiều năm hai dãy a và b không bằng nhau, tín đồ ta cũng khẳng định được sản phẩm công nghệ tự tự điển. Bằng phương pháp thêm vào thời gian cuối dãy a hoặc hàng b những bộ phận đặc biệt điện thoại tư vấn là phần tử Ø để độ dài của a và b bởi nhau, cùng coi những bộ phận Ø này nhỏ tuổi hơn toàn bộ các bộ phận khác, ta lại đưa về khẳng định thứ tự trường đoản cú điển của nhì dãy thuộc độ dài. Ví dụ:

(1, 2, 3, 4) (a, b, c) "calculator" Một hàng nhị phân độ lâu năm n là 1 trong những dãy x = x1x2…xn trong các số đó xi ϵ 0, 1 (mọi i : 1 ≤ i ≤ n).Dễ thấy: một dãy nhị phân x độ nhiều năm n là biểu diễn nhị phân của một quý giá nguyên p(x) như thế nào đó bên trong đoạn <0, 2n - 1>. Số các dãy nhị phân độ dài n = số các số nguyên ϵ <0, 2n - 1> = 2n. Ta sẽ lập chương trình liệt kê những dãy nhị phân theo trang bị tự từ điển có nghĩa là sẽ liệt kê lần lượt những dãy nhị phân biểu diễn các số nguyên theo sản phẩm tự 0, 1,…, 2n-1.

Ví dụ: khi n = 3, những dãy nhị phân độ nhiều năm 3 được liệt kê như sau:

p(x)01234567x000001010011100101110111Như vậy dãy thứ nhất sẽ là 00…0 và dãy cuối cùng sẽ là 11…1. Dìm xét rằng nếu hàng x = (x1, x2, …, xn) là dãy đang có và không hẳn dãy sau cùng thì dãy sau đó sẽ dấn được bằng phương pháp cộng thêm một ( theo cơ số 2 tất cả nhớ) vào dãy hiện tại.Ví dụ lúc n = 8:Dãy sẽ có:10010000Dãy đang có:10010111cộng thêm 1: + 1cộng thêm 1: + 1Dãy mới:10010001Dãy mới:10011000Như vậy chuyên môn sinh thông số kỹ thuật kế tiếp từ cấu hình hiện tại rất có thể mô tả như sau: Xét từ lúc cuối dãy về đầu (xét tự hàng đơn vị chức năng lên), gặp gỡ số 0 thứ nhất thì nỗ lực nó bằng số 1 và đặt toàn bộ các phần tử phía sau địa chỉ đó bằng 0.

Sponsored Links

i := n;while (i > 0) & (xi = 1) bởi vì i := i - 1;if i > 0 thenbegin xi := 1; for j := i + 1 khổng lồ n vì xj := 0;end;
Dữ liệu vào (Input): nhập từ tệp tin văn phiên bản BSTR.INP cất số nguyên dương n ≤ 30 tác dụng ra (Output): ghi ra tệp tin văn bạn dạng BSTR.OUT các dãy nhị phân độ dài n.

BSTR.INPBSTR.OUT3000 001 010 011 100 101 110 111Giải thuật:
P_1_02_1.PAS * Thuật toán sinh liệt kê những dãy nhị phân độ lâu năm nprogram Binary_Strings;const
Input
File = "BSTR.INP";Output
File = "BSTR.OUT";max = 30;varx: array<1..max> of Integer;n, i: Integer;f: Text; begin
Assign(f, Input
File); Reset(f);Read
Ln(f, n);Close(f);Assign(f, Output
File); Rewrite(f);Fill
Char(x, Size
Of(x), 0); Cấu hình ban đầu x1 = x2 = … = xn := 0

Sponsored Links

repeat Thuật toán sinhfor i := 1 lớn n vày Write(f, x); In ra cấu hình hiện tạiWrite
Ln(f);i := n; xi là phần tử cuối dãy, lùi dần i tính đến khi gặp gỡ số 0 hoặc lúc i = 0 thì dừngwhile (i > 0) & (x = 1) vị Dec(i);if i > 0 then Chưa chạm chán phải cấu hình 11…1beginx := 1; Thay xi thông qua số 1Fill
Char(x, (n - i) * Size
Of(x<1>), 0); Đặt xi + 1 = xi + 2 = … = xn := 0end;until i = 0; Đã không còn cấu hìnhClose(f);end.

Liệt kê các tập nhỏ k phần tử

Ta sẽ lập lịch trình liệt kê các tập con k phần tử của tập 1, 2, …, n theo thứ tự từ điềnVí dụ: với n = 5, k = 3, ta bắt buộc liệt kê đầy đủ 10 tập con:
1.1, 2, 3 2.1, 2, 4 3.1, 2, 5 4.1, 3, 4 5.1, 3, 56.1, 4, 5 7.2, 3, 4 8.2, 3, 5 9.2, 4, 5 10.3, 4, 5
Như vậy tập con trước tiên (cấu hình khởi tạo) là 1, 2, …, k. Thông số kỹ thuật kết thúc là n - k + 1, n - k + 2, …, n.Nhận xét: Ta sẽ in ra tập con bằng phương pháp in ra theo thứ tự các phần tử của nó theo trang bị tự tăng dần. Tự đó, ta bao gồm nhận xét giả dụ x = x1, x2, …, xk và x1 2 k thì số lượng giới hạn trên (giá trị to nhất rất có thể nhận) của xk là n, của xk-1 là n - 1, của xk-2 là n - 2, …
Cụ thể: giới hạn bên trên của xi = n - k + i;Còn tất nhiên, giới hạn dưới của xi (giá trị nhỏ nhất xi có thể nhận) là xi-1 + 1.

Như vậy nếu ta đang sẵn có một hàng x đại diện thay mặt cho một tập con, trường hợp x là thông số kỹ thuật kết thúc tức là tất cả các thành phần trong x đều đã đạt mức giới hạn bên trên thì quá trình sinh kết thúc, nếu như không thì ta bắt buộc sinh ra một dãy x mới tăng mạnh thoả mãn vừa đủ to hơn dãy cũ theo nghĩa không tồn tại một tập con k thành phần nào chen giữa chúng khi sắp thứ tự trường đoản cú điển.Ví dụ: n = 9, k = 6. Thông số kỹ thuật đang gồm x = 1, 2, 6, 7, 8, 9. Các bộ phận x3 mang lại x6 đã đạt mức giới hạn trên phải để sinh thông số kỹ thuật mới ta quan yếu sinh bằng cách tăng 1 phần tử trong những các x6, x5, x4, x3 lên được, ta đề xuất tăng x2 = 2 lên thành x2 = 3. Được thông số kỹ thuật mới là x = 1, 3, 6, 7, 8, 9. Cấu hình này vẫn thoả mãn to hơn cấu hình trước nhưng chưa thoả mãn đặc thù vừa đầy đủ lớn, muốn vậy ta lại ráng x3, x4, x5, x6 bằng các giới hạn bên dưới của nó. Tức là:
· x3 := x2 + 1 = 4· x4 := x3 + 1 = 5· x5 := x4 + 1 = 6· x6 := x5 + 1 = 7Ta được cấu hình mới x = 1, 3, 4, 5, 6, 7 là cấu hình kế tiếp. Nếu như muốn tìm tiếp, ta lại nhận thấy rằng x6 = 7 không đạt số lượng giới hạn trên, như vậy chỉ cần tăng x6 lên 1 là được x = 1, 3, 4, 5, 6, 8.Vậy kỹ thuật sinh tập con tiếp nối từ tập đã có x hoàn toàn có thể xây dựng như sau:Tìm từ thời điểm cuối dãy lên đầu cho tới lúc gặp 1 phần tử xi chưa đạt giới hạn trên n - k + i.

Xem thêm: Người sinh năm 1986 mệnh gì, tuổi gì, hợp màu nào? tuổi bính dần hợp tuổi nào, màu gì

Input: file văn bạn dạng SUBSET.INP chứa hai số nguyên dương n, k (1 ≤ k ≤ n ≤ 30) phương pháp nhau tối thiểu một dấu cách.Output: file văn bạn dạng SUBSET.OUT các tập nhỏ k thành phần của tập 1, 2, …, n.
SUBSET.INPSUBSET.OUT5 31, 2, 3 1, 2, 4 1, 2, 5 1, 3, 4 1, 3, 5 1, 4, 5 2, 3, 4 2, 3, 5 2, 4, 5 3, 4, 5Giải thuật:

Sponsored Links

P_1_02_2.PAS * Thuật toán sinh liệt kê các tập con k phần tử program Combination; const
Input
File = "SUBSET.INP";Output
File = "SUBSET.OUT";max = 30;varx: array<1..max> of Integer;n, k, i, j: Integer;f: Text; begin
Assign(f, Input
File); Reset(f);Read
Ln(f, n, k);Close(f);Assign(f, Output
File); Rewrite(f);for i := 1 lớn k do x := i; x1 := 1; x2 := 2; … ; xk := k (Cấu hình khởi tạo)repeat

In ra cấu hình hiện tạiWrite(f, "");for i := 1 lớn k - 1 vì Write(f, x, ", ");Write
Ln(f, x, "");Sinh tiếpi := k; xi là phần tử cuối dãy, lùi dần dần i cho tới khi chạm mặt một xi chưa đạt giới hạn trên n - k + iwhile (i > 0) & (x = n - k + i) bởi vì Dec(i);if i > 0 then Nếu chưa lùi đến 0 tức là chưa phải cấu hình kết thúcbegin
Inc(x); Tăng xi lên 1, Đặt các phần tử đứng sau xi bằng số lượng giới hạn dưới của nófor j := i + 1 khổng lồ k vị x := x + 1; end;until i = 0; Lùi mang lại tận 0 tức là tất cả các bộ phận đã đạt giới hạn trên - hết cấu hìnhClose(f);end.

Liệt kê những hoán vị

Ta đang lập chương trình liệt kê những hoán vị của 1, 2, …, n theo thứ tự từ bỏ điển.Ví dụ cùng với n = 4, ta nên liệt kê đủ 24 hoán vị:1.12342.12433.13244.13425.14236.14327.21348.21439.231410.234111.241312.243113.312414.314215.321416.324117.341218.342119.412320.413221.421322.423123.431224.4321Như vậy hoán vị thứ nhất sẽ là (1, 2, …, n). Hoán vị sau cùng là (n, n-1, … , 1).Hoán vị sẽ hình thành phải to hơn hoán vị hiện tại tại, không những thế nữa nên là thiến vừa đủ lớn hơn hoán vị bây giờ theo nghĩa ko thể tất cả một hoán vị nào khác chen giữa bọn chúng khi chuẩn bị thứ tự.Giả sử hoán vị hiện tại là x = (3, 2, 6, 5, 4, 1), xét 4 bộ phận cuối cùng, ta thấy bọn chúng được xếp sút dần, điều đó tức là cho mặc dù ta bao gồm hoán vị 4 bộ phận này nuốm nào, ta cũng được một hoán vị bé hơn hoán vị hiện tại!. Do đó ta đề nghị xét mang đến x2 = 2, gắng nó bởi một giá trị khác. Ta vẫn thay bằng quý hiếm nào?, ko thể là một bởi giả dụ vậy sẽ tiến hành hoán vị bé dại hơn, cấp thiết là 3 vì chưng đã tất cả x1 = 3 rồi (phần tử sau ko được lựa chọn vào những giá trị mà bộ phận trước vẫn chọn). Còn lại những giá trị 4, 5, 6. Vì đề nghị một thiến vừa đủ to hơn hiện trên nên ta lựa chọn x2 = 4. Còn những giá trị (x3, x4, x5, x6) đang lấy vào tập 2, 6, 5, 1. Cũng vày tính toàn vẹn lớn phải ta vẫn tìm biểu diễn nhỏ dại nhất của 4 số này gán đến x3, x4, x5, x6 tức là (1, 2, 5, 6). Vậy hoán vị mới sẽ là (3, 4, 1, 2, 5, 6).
Ta tất cả nhận xét gì qua lấy ví dụ như này: Đoạn cuối của thiến được xếp sút dần, số x5 = 4 là số nhỏ tuổi nhất trong đoạn cuối sút dần ưng ý điều kiện to hơn x2 = 2. Nếu đổi vị trí x5 cho x2 thì ta sẽ tiến hành x2 = 4 với đoạn cuối vẫn được sắp xếp giảm dần. Khi ấy muốn biểu diễn nhỏ nhất cho các giá trị trong đoạn cuối thì ta chỉ việc đảo ngược đoạn cuối.Trong trường đúng theo hoán vị hiện tại là (2, 1, 3, 4) thì hoán vị tiếp nối sẽ là (2, 1, 4, 3). Ta cũng hoàn toàn có thể coi thiến (2, 1, 3, 4) bao gồm đoạn cuối bớt dần, đoạn cuối này chỉ gồm 1 phần tử (4)Vậy kỹ thuật sinh hoán vị kế tiếp từ hoán vị hiện nay tại có thể xây dựng như sau:
Xác định đoạn cuối sút dần nhiều năm nhất, tìm chỉ số i của thành phần xi đứng tức thời trước đoạn cuối đó. Điều này đồng nghĩa với việc tìm kiếm từ vị trí gần cạnh cuối dãy lên đầu, chạm mặt chỉ số i trước tiên thỏa mãn xi i+1. Trường hợp toàn dãy đang là sút dần, thì kia là cấu hình cuối.i := n - 1;while (i > 0) & (xi > xi+1) bởi i := i - 1;Trong đoạn cuối giảm dần, tìm bộ phận xk bé dại nhất thoả mãn đk xk > xi. Vày đoạn cuối sút dần, vấn đề này thực hiện bằng phương pháp tìm từ thời điểm cuối dãy lên đầu gặp chỉ số k thứ nhất thoả mãn xk > xi (có thể sử dụng tìm kiếm nhị phân).k := n;

while xk i bởi vì k := k - 1;Đổi chỗ xk với xi, lật ngược thứ tự đoạn cuối bớt dần (từ xi+1 đến xk) phát triển thành tăng dần.Input: file văn bản PERMUTE.INP chứa số nguyên dương n ≤ 12Output: file văn bạn dạng PERMUTE.OUT những hoán vị của hàng (1, 2, …, n)

PERMUTE.INPPERMUTE.OUT31 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1Giải thuật:

Sponsored Links

P_1_02_3.PAS * Thuật toán sinh liệt kê hoán vịprogram Permutation; const
Input
File = "PERMUTE.INP";Output
File = "PERMUTE.OUT";max = 12;varn, i, k, a, b: Integer;x: array<1..max> of Integer;f: Text;procedure Swap(var X, Y: Integer); Thủ tục hòn đảo giá trị hai tham đổi mới X, Yvar
Temp: Integer;begin
Temp := X; X := Y; Y := Temp;end;

begin
Assign(f, Input
File); Reset(f);Read
Ln(f, n);Close(f);Assign(f, Output
File); Rewrite(f);for i := 1 khổng lồ n bởi x := i; Khởi tạo thông số kỹ thuật đầu: x1 := 1; x2 := 2; …, xn := nrepeatfor i := 1 to lớn n do Write(f, x, " "); In ra thông số kỹ thuật hoán vị hiện tạiWrite
Ln(f); i := n - 1;while (i > 0) & (x > x) vày Dec(i);if i > 0 then Chưa gặp phải hoán vị cuối (n, n-1, … ,1)begink := n; xk là phần tử cuối dãywhile x k đầu tiên to hơn xi }Swap(x, x); Đổi chỗ xk và xi

Sponsored Links

a := i + 1; b := n; Lật ngược đoạn cuối sút dần, a: đầu đoạn, b: cuối đoạnwhile a Swap(x, x); Đổi nơi xa với xbInc(a); Tiến a với lùi b, đổi vị trí tiếp cho tới khi a, b đụng nhauDec(b); end;end;until i = 0; Toàn hàng là dãy bớt dần - không sinh tiếp được - hết cấu hìnhClose(f);end.

Bài tập

Bài 1

Các lịch trình trên cách xử trí không giỏi trong trường hòa hợp tầm thường, sẽ là trường đúng theo n = 0 so với chương trình liệt kê hàng nhị phân tương tự như trong công tác liệt kê hoán vị, trường phù hợp k = 0 đối với chương trình liệt kê tổ hợp, hãy khắc phục điều đó.

Bài 2

Liệt kê các dãy nhị phân độ nhiều năm n hoàn toàn có thể coi là liệt kê những chỉnh vừa lòng lặp chập n của tập 2 thành phần 0, 1. Hãy lập chương trình:Nhập vào nhì số n cùng k, liệt kê các chỉnh phù hợp lặp chập k của 0, 1, …, n -1.Gợi ý: cố hệ cơ số 2 bằng hệ cơ số n.Bài 3Hãy liệt kê các dãy nhị phân độ dài n mà trong đó cụm chữ số "01" lộ diện đúng 2 lần.Bài 4.Nhập vào một danh sách n tên người. Liệt kê toàn bộ các cách chọn ra đúng k người trong số n người đó.
Gợi ý: desgin một ánh xạ từ bỏ tập 1, 2, …, n mang lại tập những tên người. Ví dụ xuất bản một mảng Tên: Tên<1> := "Nguyễn văn A"; Tên<2> := "Trần thị B";…. Tiếp đến liệt kê toàn bộ các tập bé k bộ phận của tập 1, 2, …, n. Chỉ có điều khi in ấn tập con, ta không in quý hiếm số 1, 3, 5 mà nỗ lực vào đó sẽ in ra Tên<1>, thương hiệu <3>, Tên<5>. Tức là in ra hình ảnh của những giá trị tìm kiếm được qua ánh xạ.

Bài 5

Liệt kê tất cả các tập bé của tập 1, 2, …, n. Hoàn toàn có thể dùng phương thức liệt kê tập bé như trên hoặc dùng phương thức liệt kê tất cả các dãy nhị phân. Từng số một trong các dãy nhị phân tương ứng với 1 phần tử được lựa chọn trong tập. Lấy một ví dụ với tập 1, 2, 3, 4 thì dãy nhị phân 1010 sẽ khớp ứng với tập bé 1, 3. Hãy lập công tác in ra toàn bộ các tập nhỏ của 1, 2, …, n theo nhị phương pháp.

Bài 6

Nhập vào list tên n người, in ra tất cả các giải pháp xếp n fan đó vào một trong những bàn.

Bài 7

Nhập vào list n các bạn nam và n chúng ta nữ, in ra tất cả các cách xếp 2n fan đó vào một trong những bàn tròn, mỗi chúng ta nam sau đó một bạn nữ.

Bài 8

Người ta hoàn toàn có thể dùng phương thức sinh nhằm liệt kê các chỉnh đúng theo không lặp chập k. Tuy vậy có một bí quyết khác là liệt kê toàn bộ các tập nhỏ k phần tử của tập hợp, sau đó in ra đầy đủ k! hoạn của nó. Hãy viết chương trình liệt kê các chỉnh phù hợp không lặp chập k của 1, 2, …, n theo cả nhì cách.

« Prev: giải mã và lập trình: §1. đề cập lại một số kiến thức đại số tổ hợp
Các khóa đào tạo và huấn luyện qua đoạn clip dành mang đến Hội viên:Python xây dựng C Java C# SQL hệ thống PHP HTML5-CSS3-Java
Script
Đăng ký kết Hội viên
Xem các nhất§6. CÂY (TREE)§1. Quá trình cơ bản khi thực hiện giải những bài toán tin học§7. Ký pháp chi phí tố, trung tố và hậu tố§3. Đệ quy và lời giải đệ quy§2. Phương pháp sinh (GENERATION)§3.1. Dãy con đối chọi điệu tăng dài nhất§3. Thuật toán tảo lui§2. Phân tích thời gian thực hiện nay giải thuật§4. Nghệ thuật nhánh cận§6. Chu trình Euler, lối đi Euler, vật thị Eulerreport this ad