None

Hàm sinh kế tiếp

Tác giả: Từ Nghĩa

    Với sự phát triển “siêu to khổng lồ” của mạng Neuron (Neural Network) khi đi nghiên cứu LSTM với model Sequence generation hay Sequence to sequence trong bài toán tự sinh câu tự nhiên cho các ứng dụng trả lời tự động, tóm tắc văn bản, auto caption … Liên quan tới các loại “sinh sinh” làm mình hồi tưởng lại một kiến thức đã học  trong toán rời rạc đó là hàm sinh kế tiếp, nghe tên nó có chút liên quan với công nghệ sinh câu phải không các bạn cheeky

    Cụ thể như thế nào, bài viết này mình sẽ nhắc lại hàm sinh kế tiếp để ôn lại kỷ niệm thời đại học.


Giới thiệu:

    Trong bài toán liệt kê như:

        + Liệt kệ danh sách các chuỗi nhị phân có độ dài bằng n.

        + Liệt kê các cặp thi đấu trong danh sách có 5 đội bóng.

        + Liệt kê các cách đi từ điểm A đến điểm D sao cho không qua điểm C (với một đồ thị đã cho).

        …

    Mình sẽ nhắc lại 2 nguyên tắc trong bài toán liệt kê:

        + Nguyên tắc 1: Các cấu hình không được trùng lặp

        + Nguyên tắc 2: Không bỏ sót cấu hình

    Để giải các bài toán liệt kê tổ hợp này, trong lập trình chúng ta thường dùng hai cách là quay lui (đệ quy) và hàm sinh kế tiếp.

    * Với hàm sinh kế tiếp, chúng ta cần xây dựng 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ó.

    Như vậy để áp dụng thuật toán sinh kế tiếp, bài toán cần phải xác định:

        + Cấu hình đầu tiên và cấu hình cuối cùng (việc này thường khá đơn giản)

        + Quy tắc sinh dãy 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à cấu hình thoả mãn và liền kề với cấu hình trước nó với các phần tử có thay đổi theo thứ tự từ trước ra sau, từ nhỏ tới lớn. ( phức tạp hơn ý thứ nhât wink )

Thông qua phần mô tả ở trên, thuật toán sinh kế tiếp được cài đặt dạng như sau:


""" 
Input:
    curr: cấu hình hiện tại
	m   : số lượng phần tử trong cấu hình
	      thông tin không gian liên quan
Output:
	next_curr: cấu hình kế tiếp
"""
def next_generate([cấu hình hiện tại], [thông tin không gian]):
    if [cấu hình là cuối cùng]:
        return [cấu hình hiện tại]
    # tìm các vị trí phần tử sẽ thay đổi trong cấu hình hiện tại
    # thay đổi các phần tử trong cấu hình hiện tại để tạo ra cấu hình kế tiếp
    return [cấu hình kế tiếp]

    Khá đơn giản phải không nào cool

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

 

Ứng dụng:

Bài 1

Bài Hello world của thuật toán sinh kế tiếp mình sẽ chọn là: Chuỗi nhị phân kế tiếp có độ dài n.

Input:

    + n: Độ dài 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 kế tiếp

            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 dễ dàng xác định:

+ Chuỗi đầu tiên: [0, 0, 0 ,0]

+ Chuỗi cuối cùng: [1, 1, 1, 1]

+ Quy luật sinh chúng ta xác định được ngay là chuỗi sau bằng chuỗi trước thêm 1 theo hệ nhị phân.

Đến đây các bạn sẽ thấy rất là đơn giản phải không nào, một dòng code là xong wink

next_curr = bin(0b1011 + 0b1)

Tuy nhiên, mình sẽ phân tích và xây dựng thuật toán ở mức tổng quát để có thể ứng dụng được vào những bài toán khó hơn nhé:

Cộng 1 vào chuỗi nhị phân chúng ta sẽ làm theo cách:

    + Đổi bit 0 ở phía phải cùng thành 1.

    + Đổi các bit 1 sau nó về 0 nếu có.

Phân tích xong, đến lúc cài đặt chương trình nào laugh


def next_generate(curr, n):
   if set(curr) == {1}:  # Nếu toàn bộ bit 1 thì đã là chuỗi cuối cùng
       return curr
   i = n - 1  # Bắt đầu từ vị trí phải cùng
   while curr[i]:  # Trong khi bằng 1 thì đặt lại bằng 0
       curr[i] = 0
       i -= 1
   curr[i] = 1  # Đặt vị trí 0 bên phải cùng về bằng 1
   return curr  # Trả về chuỗi kế tiếp


if __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 phải không các bạn smiley

 

Bài 2

    Lần này mình sẽ đưa ra một ví dụ mang tính ứng dụng thực tế hơn chút nhé:

    Khi xem một trận bóng đá hay ví dụ U23 Châu Á chẳng hạn, một câu hỏi nhỏ đặt ra là coi hết trận này thì mình sẽ coi trận nào nữa (trận tiếp theo trong cùng bản đấu và bảng có 4 đội) 

    Bài toán khái quát của ví dụ này là: Tìm tổ hợp kế tiếp của k phần tử trong tập n phần. Đó là k = 2 và n = 4 phải không nào.

    Chúng ta cùng đi phân tích bài toán.

    Input:

        + n: Số lượng 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: độ dài 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: cấu hình kế tiếp

             vd: tiếp theo có thể được xem next_curr = ['Việt Nam', 'UAE']

    Theo luật lập cấu hình từ trái sang phải, từ nhỏ tới lớn thì chúng ta xác định được:

        + Cấu hình đầu tiên: ['Triều Tiên', 'Việt Nam']

        + Cấu hình cuối cùng: [ 'UAE', 'Jordan']

        + Quy luật sinh kế tiếp là cấu hình sau lớn hơn cấu hình trước theo chuỗi thứ tự chỉ số đại diện.

    Gọi 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ố đại diện các phần tử của tập S và tổ hợp c = {$\ c_0, c_1, ..., c_{k-1} $ }  với $\ c_i $ ∈ a:

        + $\ c_0 < c_1 < ... < c_{k-1} $

        + $\ c_i(c_i^0c_i^1...c_i^{k-1}) < c_j(c_j^0c_j^1...c_j^{k-1})$ với $\ i < j $

    Trong bài này: s = ['Triều Tiên', 'Việt Nam', 'UAE', 'Jordan'] 

                       và a = {0 ,               1 ,              2,         3         }

    Các tổ hợp sẽ là (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)

    Vậy khi sinh kế tiếp ta tìm cách thay đổi theo chiều tăng ưu tiên các phần tử từ phía bên phải cùng

    Và thuật toán sinh tổ hợp kế tiếp sẽ thực hiện:

        + Tìm kiếm phần tử vị trí phía bên phải cùng (ci) còn có thể tăng được 

                $\ c_i = n - k + a_i $

        + Tăng phần tử $\ c_i $ đó lên 1

               $ \ c_i += 1 $

        + Cài đặt lại các phần tử phía sau: $\ c_j $ (i < j) nếu có theo thứ tự tăng dần lên 1 bắt đầu từ $\ c_i $

               $\ c_j = c_i + j - i $

    Cài đặt thuật toán chạy thử nhé wink


def next_generate(n, basket, k, curr):
   pos = k - 1
   while curr[pos] == basket[n - k + pos]:  # Tìm vị trí phải cùng có thể tăng được
       pos -= 1

   if pos < 0:  # Không tìm thấy => là cấu hình cuối cùng
       return curr

   for j in range(pos, k):
       if j == pos:
           curr[j] = basket[basket.index(curr[j]) + 1]  # tăng phần tử lại vị trí pos lên 1
       else:
           curr[j] = basket[basket.index(curr[pos]) + j - pos]  # cài đặt lại các phần tử theo sau
   return curr


if __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']

    Kết quả đúng rồi phải không các bạn, nhưng chỉ đúng trong chương trình thôi còn thực tế thì tuỳ vào sự sắp xếp của ban tổ chức nhé cheeky

 

Kết luận

    Trong bài toán liệt kê, sinh kế tiếp (next generation) và quay lui (backtracking) là nhữ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 hơn khi sử dụng như trường hợp chỉ cần một vài cấu hình mong muốn chứ không phải toàn bộ, mặt dù thường cùng bài toán cài đặt với next generation khó 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 cho câu hỏi “Next generation có liên quan gì đến bài toán sinh câu tự động” rồi :))

    Chào thân ái các bạn và hẹn gặp lại wink

 

Tham khảo

    + [1] Nguyễn Đức Nghĩa và Nguyễn Tô Thành, Toán rời rạc, NXB Giáo dục, 1997.