Tổ hợp, chỉnh hợp và bài toán đếm cơ bản


#math #combination #accordant #vi

Background

Bạn có nhớ gì về hồi cấp 3 ko? Ý mình ko phải là hình ảnh em gái xinh nhất khối mặc áo trong và ngoài có mã màu lần lượt là #000 và #fff đi trong mưa, mà là ít kiến thức về tổ hợp, chỉnh hợp hồi lớp 12 cơ.

Nếu vững kiến thức này, gần thì bạn sẽ rất nhẹ nhàng làm những bài test nhỏ kiểu như trên codility, paiza. Xa thì có thể ăn chắc 1 trong vài bài test khi đi xin việc :v

Tổ hợp và chỉnh hợp

  • Tổ hợp: là cách chọn ra K phần tử từ N phần tử (1 <= K <= N), không quan tâm đến thứ tự. Ví dụ, “Các thầy hãy chọn cho tôi 10 giáo viên nữ để đi tiếp khách”. Lúc này thì cứ chọn đủ 10 giáo viên là được, ko quan tâm ai trước ai sau, thì là 1 dạng của tổ hợp.
  • Chỉnh hợp: Tương tự như trên, khác là có quan tâm đến thứ tự. Ví dụ, “Các thầy hãy chọn cho tôi 3 giáo viên để đảm nhiệm các vị trí Phó hiệu trưởng, Bí thư nhà trường và Cán bộ công đoàn”. Lúc này ai vào vị trí nào thì đều có thứ tự rồi, và chỉ cần đổi thứ tự là sẽ có case khác nhau.
  • Vậy, dễ dàng thấy rằng, Số Chỉnh hợp luôn nhiều hơn Số Tổ hợp
  • Công thức Số Chỉnh hợp =
  • Công thức Số Tổ hợp = Số Chỉnh hợp / K! =
  • Tại sao? Các bạn không cần nhớ lại làm gì, mình sẽ trình bày luôn phía dưới. :v

Số Chỉnh hợp =

Quay lại bài toán chọn 10 giáo viên trong số 30 giáo viên để đi tiếp khách. Như vậy, N = 30 và K = 10. Cụ thể:

  • Giáo viên thứ nhất có 30 cách chọn.
  • Giáo viên thứ hai có 29 cách chọn.
  • Giáo viên thứ ba có 28 cách chọn.
  • ….
  • Giáo viên thứ 10 có 21 cách chọn.

Số cách chọn là: 30 * 29 * ... * 21 .
Tổng quát thành: N * (N-1) * ... * (N - K + 1).
Vậy số chỉnh hợp = N * (N-1) * ... * (N - K + 1).

Nhân cả 2 vế với với một lượng (N - K) * (N - K -1) * ... * 2 * 1, hay chính là (N - K)!, thu được:

số chỉnh hợp * (N - K)! = N * (N-1) * ... * (N - K + 1) * (N - K) * (N - K -1) * ... * 2 * 1.

Mà vế phải chính là N!, nên chia cả 2 vế cho (N - K)!, thu:

Số Chỉnh hợp = (ĐPCM)

Số Tổ hợp = Số Chỉnh hợp / K! =

Nhớ lại là tổ hợp thì ko quan tâm đến thứ tự. Nghĩa là với bộ 3 số {1, 2, 3} thì ta có số chỉnh hợp là 3! / (3-3)! = 6 (quy ước 0! = 1)

Nhưng số tổ hợp thì chỉ là 1 mà thôi, vì ko quan tâm tới thứ tự mà, nên cho dù có bao nhiêu cách sắp xếp khác nhau thì cũng chỉ là một tổ hợp mà thôi.

Tổng quát lên, số tổ hợp = số chỉnh hợp / số cách sắp xếp khác nhau của K phần tử.

số cách sắp xếp khác nhau của K phần tử chính bằng số hoán vị của K, hay K!, nên:

Số Tổ hợp = Số Chỉnh hợp / K!.

Thay Số Chỉnh hợp = thu:

Số Tổ hợp = (ĐPCM)

Áp dụng cho bài toán đếm số tương tự

  • Một số được cho là tương tự số ban đầu nếu số đó được tạo bởi các chữ số giống với các chữ số của số đã cho và ko xét nếu 0 ở đầu. Ví dụ 113 có 3 số tương tự là 113, 131, 311. Nhưng 100 chỉ có 1 số tương tự là 100 thôi, vì nếu 001 hay 010 thì ko hợp lệ.
  • Vậy có cách nào tổng quát để tính số lượng số tương tự của 1 số cho trước không?
  • Trước hết hãy cùng xem xét một bài toán có tên Bookkeeper Rule dưới đây.

Bookkeeper Rule

Là công thức tính số cách sắp xếp các chữ cái trong từ bookkeeper theo các cách khác nhau. Ví dụ ta sẽ có bokokeeper, bkookeeper

Công thức được viết thành:
Số cách xếp = = 302400 cách xếp.

Các con số trên lấy ở đâu ra?

  • 10 = độ dài của xâu bookkeeper
  • 1, 2, 2, 3, 1, 1 lần lượt là số lần xuất hiện của b, o, k, e, p, r trong xâu bookkeeper.

Như vậy, nếu áp dụng Bookkeeper rule cho bài toán số tương tự, ta phải xét thêm trường hợp số 0 đứng đầu. Do cứ có số 0 đứng đầu thì số tạo thành là ko hợp lệ, nên mọi cách sắp xếp của các chữ số còn lại trong trường hợp có số 0 ở đầu là không hợp lệ.

Vậy đơn giản là chỉ cần lấy tổng các số tương tự trừ đi tổng số cách mà có 0 đứng đầu là sẽ thu được kết quả đúng.

Và cũng có thể áp dụng Bookkeeper rule cho các chữ số còn lại trong trường hợp có số 0 ở đầu để thu được số các số mà bắt đầu bằng 0.

Vậy có thể viết thành công thức tổng quát như sau:

numbers_start_with_0 = if(original_number.contains(0)) bookkeeper(original_number.remove_one(0)) else 0
simillar_numbers = bookkeeper(original_number) - numbers_start_with_0

Mình có viết một đoạn code bằng Ruby minh hoạ cho công thức trên như sau:

# Calculate number of Similar Numbers
# 112 has 112, 121, 211 (3 similar numbers)
# 100 has 100 (1 similar number)
# Given integer a (1 <= a <= 2^32)
# Calculate number of similar numbers of a

def permute(n)
  return 1 if n == 0
  (1..n).reduce(:*)
end

# BookKeeper Rule
# http://web.mit.edu/neboat/Public/6.042/counting3.pdf
#
# group_digits has format:
# {digit1 => number_digits1, digit2 => number_digits2}
def bookkeeper(group_digits)
  number_digits       = 0
  denominator_permute = 1
  group_digits.each do |_, n_digits|
    number_digits       += n_digits
    denominator_permute *= permute(n_digits)
  end
  permute(number_digits) / denominator_permute
end

def solution(a)
  digits       = a.to_s.split('')
  group_digits = Hash.new(0).tap { |h| digits.each { |d| h[d.to_i] += 1 } }
  total_cases  = bookkeeper(group_digits)

  # Remove all similar numbers that start with 0
  # Means: If similar number start with 0,
  # all other similar numbers that is created by other digits will be invalid
  unless group_digits[0] == 0
    group_digits[0] = group_digits[0] - 1
    total_cases     -= bookkeeper(group_digits)
  end

  total_cases
end

Make #cấp3 great again!



Related Posts

Tìm hiểu bộ lọc Bloom (Bloom filter) và một số ứng dụng dưới con mắt đời thường

Bloom filter không phải là một cài đặt cụ thể, nó là một tư tưởng thoả mãn tính chất False positive.

Higher-Order Function (HOF) và Currying

HOF và Currying là hai kỹ thuật không khó, thậm chí bạn đang dùng nó hàng ngày mà không để ý. Cùng tìm hiểu chúng thông qua một số ví dụ.

Kỹ thuật sửa lỗi Reed - Solomon

Tìm hiểu một số khái niệm và tính chất của kỹ thuật sửa lỗi Reed - Solomon, với sự xuất hiện của Ưng Hoàng Phúc, Ngọc Trinh :v

Vài suy nghĩ về nghề Lập Trình Viên (LTV)

Nghề LTV dưới góc nhìn của người viết. Liệu nó có phải là nghề "đáng làm" hay không?

Xây dựng ứng dụng chat sử dụng websocket có khó không?

A-to-Z Xây dựng ứng dụng realtime chat sử dụng action cable rails 5

Pinterest đã thực hiện scaled MySQL của họ như thế nào

Bài viết lược dịch từ Sharding Pinterest How we scaled our MySQL fleet, một bài viết theo mình đánh giá là rất chất lượng, và có nhiều giá trị có thể tham khảo.

Thực hiện benchmark (BM) MySQL InnoDB Buffer Pool(BP) trước và sau khi được warmup

Mình thực hiện BM này cho chính [tool mình viết](https://github.com/manhdaovan/mysql_warmup), cũng là 1 tool đơn giản thôi, tiện thể đem kết quả lên khoe với mọi người luôn.

So sánh các câu lệnh warmup primary key vào buffer pool với engine InnoDB mysql

Buffer pool(BF) của mysql quả thực có nhiều lợi ích, và việc warm up BP luôn là việc nên làm đầu tiên mỗi khi start/reload/create new mysql. Tuy nhiên, "touch" thế nào cho tối ưu nhất? Trong quá trình thực hiện benchmark cho [tool này](https://github.com/manhdaovan/mysql_warmup), người viết thấy có 1 số điều thú vị như dưới đây.

Muốn đi Nhật - Cần làm gì?

Kinh nghiệm bản thân về việc chuẩn bị sang vùng kinh tế mới :v