Cần công thức tính một dạng Tổ hợp

Liên hệ QC

congthanh6868

Thành viên thường trực
Tham gia
30/5/09
Bài viết
322
Được thích
63
Chào các bạn, mình đang gặp yêu cầu như sau:

Trong 100 số từ: 00 đến 99, liệt kê những nhóm có 30 số không trùng nhau.
Ví dụ:
00 01 ...... 28 29
00 01 ...... 28 30
------
------
69 71 ...... 98 99
70 71 ...... 98 99

Từng nhóm có thể ở trong 1 cell hoặc ở 30 cell.

Mong các bạn phát triển giúp công thức.

Cám ơn các bạn nhiều.
 
Chào các bạn, mình đang gặp yêu cầu như sau:

Trong 100 số từ: 00 đến 99, liệt kê những nhóm có 30 số không trùng nhau.
Ví dụ:
00 01 ...... 28 29
00 01 ...... 28 30
------
------
69 71 ...... 98 99
70 71 ...... 98 99

Từng nhóm có thể ở trong 1 cell hoặc ở 30 cell.

Mong các bạn phát triển giúp công thức.

Cám ơn các bạn nhiều.
Cái này có thể làm được nhưng bạn đưa file lên đi để khỏi hỏi lại lần 2
 
gửi các bạn file đính kèm. Mong nhận được sự giúp đỡ của các bạn.
 

File đính kèm

  • Bai toan dang tinh To hop.xls
    13.5 KB · Đọc: 59
Chương trình sau (bạn nên chọn và chép vô Macro của Excel) sẽ chọn 30 số từ 0 đến 99, ngẫu nhiên, không trùng lặp và in vào các ô đầu của hàng đang chứa ô hoạt động.

Sub Random()
Randomize
Dim a(0 To 99) As Byte
Set c = Cells
For i! = 0 To 99
a(i) = i
Next
For i = 0 To 99
k! = Int(Rnd() * 100)
t! = a(i): a(i) = a(k): a(k) = t
Next
nh! = ActiveCell.Row
For i = 1 To 30
c(nh, i) = a(i)
Next
End Sub
 
Chào các bạn, mình đang gặp yêu cầu như sau:

Trong 100 số từ: 00 đến 99, liệt kê những nhóm có 30 số không trùng nhau.
Ví dụ:
00 01 ...... 28 29
00 01 ...... 28 30
------
------
69 71 ...... 98 99
70 71 ...... 98 99

Từng nhóm có thể ở trong 1 cell hoặc ở 30 cell.

Mong các bạn phát triển giúp công thức.

Cám ơn các bạn nhiều.


Chả cần dùng đít to đít nhỏ đít thon gì cả. Thuật toán hoàn toàn đơn giản (giải thích trong hàm). Số vòng lặp luôn bằng số phần tử cần chọn. Dĩ nhiên phần tử được chọn sẽ không được phép chọn trong các lần tiếp theo, tức phải loại bỏ. Dùng đít to đít nhỏ với Exists hoặc không (bẫy lỗi) sẽ gặp trường hợp trùng thì "phí" một vòng lặp, tức số vòng lặp có thể > số phần tử cần chọn. Hàm dưới đây không dùng thêm công cụ nào cả.
Mã:
Function Draw(Arr, Amount As Long)
' hàm chọn lần lượt Amount phần tử của mảng Arr. Việc chọn phần tử của mảng Arr đồng nghĩa 
với việc chọn chỉ số của phần
' tử đó trong mảng
' Ta dùng vòng lặp có Amount bước. Trong mỗi bước ta chọn 1 chỉ số, tức 1 phần tử. Ta loại phần 
tử được chọn
' khỏi lần chọn tiếp theo bằng cách ghi phần tử thứ k trong mảng nguồn vào vị trí có chỉ số vừa 
được chọn và tăng
' thêm 1 đơn vị cận dưới của khoảng chỉ số thao tác trong vòng lặp sau. Bằng cách này trong mỗi 
vòng lặp ta chỉ
' chọn trong những phần tử chưa được chọn. Luôn có Amount vòng lặp. Dùng từ điển có thể số 
vòng lặp sẽ > Amount
Dim index As Long, k As Long, d As Long, c As Long, tmpArr, original
    If Amount > UBound(Arr) - LBound(Arr) + 1 Then Exit Function
    original = Arr
    
    ReDim tmpArr(1 To Amount)
    d = LBound(original)
    c = UBound(original)
    Randomize
    For k = 1 To Amount
        ' chọn chỉ số trong khoảng chỉ số hiện thời
        index = Int(Rnd() * (c - d + 1)) + d
        ' ghi phần tư được chọn vào mảng kết quả
        tmpArr(k) = original(index)
        ' loại phân tử vừa chọn bằng cách thay thế nó bằng phần tử thứ k trong mảng nguồn,
        ' tức phần tử có chỉ số k + LBound(Arr) - 1
        original(index) = original(k + LBound(original) - 1)
        ' tăng cận dưới của khoảng chỉ số thao tác
        d = d + 1
    Next k
    Draw = tmpArr
End Function
Các phần tử của mảng không nhất thiết là số. VD. đó là danh sách mã, danh sách học sinh không trùng.
 
Lần chỉnh sửa cuối:
Chả cần dùng đít to đít nhỏ đít thon gì cả. Thuật toán hoàn toàn đơn giản (giải thích trong hàm). Số vòng lặp luôn bằng số phần tử cần chọn. Dĩ nhiên phần tử được chọn sẽ không được phép chọn trong các lần tiếp theo, tức phải loại bỏ. Dùng đít to đít nhỏ với Exists hoặc không (bẫy lỗi) sẽ gặp trường hợp trùng thì "phí" một vòng lặp, tức số vòng lặp có thể > số phần tử cần chọn. Hàm dưới đây không dùng thêm công cụ nào cả.

Chuẩn và cho tốc độ nhanh hơn dic nhỏ dic to lun,

Thay đổi, thay đổi ...... chứ đừng nghĩ là xưa cũ là hay là chuẩn, GPE đã có thêm 1 hàm UDF mới để lựa chọn sử dụng thay cái cái cũ đi

chỉ góp ý chút:
Có thể không cần
d = d + 1
chỉ cần thay d ở chỗ random theo cả Lbound và k là được

// và bài này cho chọn k phần tử ngẫu nhiên trong tập n phần tử--- TUY nhiên hình như chủ topic hỏi khác (song những người trả lời trước đã lái sang vấn đề này)
 
Lần chỉnh sửa cuối:
Chuẩn và cho tốc độ nhanh hơn dic nhỏ dic to lun,

Thay đổi, thay đổi ...... chứ đừng nghĩ là xưa cũ là hay là chuẩn, GPE đã có thêm 1 hàm UDF mới để lựa chọn sử dụng thay cái cái cũ đi

chỉ góp ý chút:
Có thể không cần
d = d + 1
chỉ cần thay d ở chỗ random theo cả Lbound và k là được

// và bài này cho chọn k phần tử ngẫu nhiên trong tập n phần tử--- TUY nhiên hình như chủ topic hỏi khác (song những người trả lời trước đã lái sang vấn đề này)

Chính xác. Cái này là kiểu viết nhanh nhanh, "viết vội trên đầu gối", nghĩ tới đâu viết tới đó nên chưa trau chuốt. Cám ơn bạn đã bổ sung.

Sau một hồi suy nghĩ thì tôi thấy thế này:
Với
Mã:
index = Int(Rnd() * (c - d + 1)) + d
...
d = d + 1
Ta có 1 phép nhân, 2 phép cộng trừ (c - d + 1) + 1 phép cộng ( ... + d) + 1 phép cộng (d = d + 1), tổng cộng 1 phép nhân và 4 phép cộng trừ.
Nếu sửa thành
Mã:
index = Int(Rnd() * (c - d - k + 2)) + d + k - 1
Thì có 1 phép nhân và 6 phép cộng trừ.
Nếu đúng thế thì để code cũ ngoài việc giảm phép cộng trừ cho bộ vi xử lý thì còn thấy rõ "ý đồ" thuật Toán hơn.
Tất nhiên đây chỉ là ý kiến chủ quan của tôi thôi.

Nhân tiện đây tôi cũng giải thích luôn:
Mã:
d = LBound(original)
c = UBound(original)
Ta nên nhớ rằng đọc giá trị từ biến ra bao giờ cũng nhanh hơn là đọc từ thuộc tính của đối tượng hay gọi hàm. Vậy nếu ta cần dùng một giá trị không đổi nhiều lần thì trước tiên ta đọc vào biến sau đó nhiều lần đọc từ biến ra.
 
Lần chỉnh sửa cuối:
Chả cần dùng đít to đít nhỏ đít thon gì cả. Thuật toán hoàn toàn đơn giản (giải thích trong hàm). Số vòng lặp luôn bằng số phần tử cần chọn. Dĩ nhiên phần tử được chọn sẽ không được phép chọn trong các lần tiếp theo, tức phải loại bỏ. Dùng đít to đít nhỏ với Exists hoặc không (bẫy lỗi) sẽ gặp trường hợp trùng thì "phí" một vòng lặp, tức số vòng lặp có thể > số phần tử cần chọn. Hàm dưới đây không dùng thêm công cụ nào cả.
Mã:
Function Draw(Arr, Amount As Long)
' hàm chọn lần lượt Amount phần tử của mảng Arr. Việc chọn phần tử của mảng Arr đồng nghĩa 
với việc chọn chỉ số của phần
' tử đó trong mảng
' Ta dùng vòng lặp có Amount bước. Trong mỗi bước ta chọn 1 chỉ số, tức 1 phần tử. Ta loại phần 
tử được chọn
' khỏi lần chọn tiếp theo bằng cách ghi phần tử thứ k trong mảng nguồn vào vị trí có chỉ số vừa 
được chọn và tăng
' thêm 1 đơn vị cận dưới của khoảng chỉ số thao tác trong vòng lặp sau. Bằng cách này trong mỗi 
vòng lặp ta chỉ
' chọn trong những phần tử chưa được chọn. Luôn có Amount vòng lặp. Dùng từ điển có thể số 
vòng lặp sẽ > Amount
Dim index As Long, k As Long, d As Long, c As Long, tmpArr, original
    If Amount > UBound(Arr) - LBound(Arr) + 1 Then Exit Function
    original = Arr
    
    ReDim tmpArr(1 To Amount)
    d = LBound(original)
    c = UBound(original)
    Randomize
    For k = 1 To Amount
        ' chọn chỉ số trong khoảng chỉ số hiện thời
        index = Int(Rnd() * (c - d + 1)) + d
        ' ghi phần tư được chọn vào mảng kết quả
        tmpArr(k) = original(index)
        ' loại phân tử vừa chọn bằng cách thay thế nó bằng phần tử thứ k trong mảng nguồn,
        ' tức phần tử có chỉ số k + LBound(Arr) - 1
        original(index) = original(k + LBound(original) - 1)
        ' tăng cận dưới của khoảng chỉ số thao tác
        d = d + 1
    Next k
    Draw = tmpArr
End Function
Các phần tử của mảng không nhất thiết là số. VD. đó là danh sách mã, danh sách học sinh không trùng.
Quả đúng là 1 giải thuật rất thông minh
Đã test thử với 100000 số, lấy ra 60000 số.. so sánh với hàm UniqueRandomNum trước đây thì cái của bạn nhanh hơn ít nhất 7 lần
Tuy nhiên nếu dùng, chắc phải sửa lại đôi chút, vì:
- Biến Arr là cái ta không có sẳn
- Nếu Arr lấy từ CSDL của Excel thì Arr luôn là mảng 2 chiều
vân vân...
Nhưng nói chung cũng không quan trọng lắm ---> Giải thuật vẫn thế ---> Tốc độ cao mới là cái đáng để học hỏi từ code này
Ẹc... Ẹc...
 
gửi các bạn file đính kèm. Mong nhận được sự giúp đỡ của các bạn.
Tôi nghĩ NẾU đây là bài toán yêu cầu LIỆT KÊ TẤT CẢ CÁC TỔ HỢP thì nó là bài toán bất khả thi, vì số tổ hợp sinh ra là:
Combin(100, 30) = 2.93723398216109E+25
(~ Hai mươi chín triệu tỷ tỷ)
 
Tôi nghĩ NẾU đây là bài toán yêu cầu LIỆT KÊ TẤT CẢ CÁC TỔ HỢP thì nó là bài toán bất khả thi, vì số tổ hợp sinh ra là:
Combin(100, 30) = 2.93723398216109E+25
(~ Hai mươi chín triệu tỷ tỷ)

Cám ơn bạn.
Đúng là mục đích mình muốn Liệt kê tất cả tổ hợp. Nhưng nay biết được Công thức tính tổng số tổ hợp và biết được Tổng số to như vậy thì mình cũng không dám liệt kê nữa.
Cám ơn bạn, cám ơn Diễn đàn.
 
Quả đúng là 1 giải thuật rất thông minh
Đã test thử với 100000 số, lấy ra 60000 số.. so sánh với hàm UniqueRandomNum trước đây thì cái của bạn nhanh hơn ít nhất 7 lần
Tuy nhiên nếu dùng, chắc phải sửa lại đôi chút, vì:
- Biến Arr là cái ta không có sẳn
- Nếu Arr lấy từ CSDL của Excel thì Arr luôn là mảng 2 chiều
vân vân...
Nhưng nói chung cũng không quan trọng lắm ---> Giải thuật vẫn thế ---> Tốc độ cao mới là cái đáng để học hỏi từ code này
Ẹc... Ẹc...
NDU có thể cụ thể code thành 1 file ex giúp được không. Chỉ cần lấy 3 số ngẫu nhiên không trùng từ Arr=Array(1,2,3,4,5,9).
Và cụ thể phần thay cận dưới giúp.
Sao tôi gán code trên vào file mà vẫn trùng.
Cám ơn nhiều.
 
NDU có thể cụ thể code thành 1 file ex giúp được không. Chỉ cần lấy 3 số ngẫu nhiên không trùng từ Arr=Array(1,2,3,4,5,9).
Và cụ thể phần thay cận dưới giúp.
Sao tôi gán code trên vào file mà vẫn trùng.
Cám ơn nhiều.

Bạn thử up file bạn đã thử xem sao,

biết đâu ít ra mọi người học được cái lỗi đó
 
Cám ơn bạn.
Đúng là mục đích mình muốn Liệt kê tất cả tổ hợp. Nhưng nay biết được Công thức tính tổng số tổ hợp và biết được Tổng số to như vậy thì mình cũng không dám liệt kê nữa.
Cám ơn bạn, cám ơn Diễn đàn.

Tại sao không dám liệt kê,
Liệt kê đi sợ gì, vấn đề biết vậy thì bạn liệt kê ít đi - số liệu nhỏ nhỏ thôi, hoặc thoả mãn điều kiện thôi ví như chủ đề này : http://www.giaiphapexcel.com/forum/...á-trị-dựa-vào-3-điều-kiện&p=408802#post408802
 
Lần chỉnh sửa cuối:
Bạn thử up file bạn đã thử xem sao,

biết đâu ít ra mọi người học được cái lỗi đó
Không biết tôi có làm sai chỗ nào.
PHP:
Function Draw(Arr, Amount As Long)
 ' hàm ch?n l?n lu?t Amount ph?n t? c?a m?ng Arr. Vi?c ch?n ph?n t? c?a m?ng Arr d?ng nghia'
 'v?i vi?c ch?n ch? s? c?a ph?n'
' t? dó trong m?ng
 ' Ta dùng vòng l?p có Amount bu?c. Trong m?i bu?c ta ch?n 1 ch? s?, t?c 1 ph?n t?. Ta lo?i ph?n'
't? du?c ch?n
' kh?i l?n ch?n ti?p theo b?ng cách ghi ph?n t? th? k trong m?ng ngu?n vào v? trí có ch? s? v?a
'du?c ch?n và tang
' thêm 1 don v? c?n du?i c?a kho?ng ch? s? thao tác trong vòng l?p sau. B?ng cách này trong m?i
'vòng l?p ta ch?
' ch?n trong nh?ng ph?n t? chua du?c ch?n. Luôn có Amount vòng l?p. Dùng t? di?n có th? s?
'vòng l?p s? > Amount
Dim index As Long, k As Long, d As Long, c As Long, tmpArr, original
    If Amount > UBound(Arr) - LBound(Arr) + 1 Then Exit Function
    original = Arr
    
    ReDim tmpArr(1 To Amount)
    d = LBound(original)
    c = UBound(original)
    Randomize
    For k = 1 To Amount
        ' ch?n ch? s? trong kho?ng ch? s? hi?n th?i
        'index = Int(Rnd() * (c - d + 1)) + d
        index = Int(Rnd() * (c - d - k + 2)) + d + k - 1
        ' ghi ph?n tu du?c ch?n vào m?ng k?t qu?
        tmpArr(k) = original(index)
         ' lo?i phân t? v?a ch?n b?ng cách thay th? nó b?ng ph?n t? th? k trong m?ng ngu?n,'
        ' t?c ph?n t? có ch? s? k + LBound(Arr) - 1
        original(index) = original(k + LBound(original) - 1)
         ' tang c?n du?i c?a kho?ng ch? s? thao tác'
         d = d + 1
    Next k
    Draw = tmpArr
End Function
Sub Test1()
Dim sArr(), i&, iSo&
sArr = Array(1, 2, 3, 4, 5, 9)
iSo = 3
For i = 1 To iSo
  Cells(i, 2) = Draw(sArr, iSo)(i)
Next i
End Sub
 
Lần chỉnh sửa cuối:
Không biết tôi có làm sai chỗ nào.
PHP:
Sub Test1()
Dim sArr(), i&, iSo&
sArr = Array(1, 2, 3, 4, 5, 9)
iSo = 3
For i = 1 To iSo
  Cells(i, 2) = Draw(sArr, iSo)(i)
Next i
End Sub

Thay sub trên thành

PHP:
Sub Test1()
Dim sArr(), tArr(), i&, iSo&
sArr = Array(1, 2, 3, 4, 5, 9)
iSo = 3
tArr = Draw(sArr, iSo)
For i = 1 To iSo
  Cells(i, 2) = tArr(i)
Next i
End Sub

Tại sao thế thì tôi không biết, nhưng làm theo bài thì phải vậy
 
Không biết tôi có làm sai chỗ nào.

For i = 1 To iSo
Cells(i, 2) = Draw(sArr, iSo)(i)
Next i
End Sub[/PHP]

Mỗi lần gọi lại hàm Draw nó sẽ tính ra 1 số khác nhau, tuy nhiên vị trí của từng chữ số vẫn có thể trùng. Cách làn như anh Vodoi đã chỉ. Nghĩa là gọi hàm 1 lần gán vào biến tạm để xử lý
 
Thuật toán của siwtom tôi hiểu lờ mờ rằng:
Sau khi lấy được phần tử kết quả thứ k trong trong vòng lặp gán vào tmp, thì thay phần tử đó trong original bằng giá trị phần tử thứ k trong original.

Nhưng công thức rnd() vẫn lấy từ đầu đến cuối của original, nên vẫn còn khả năng lấy lần 2, lần 3.

Nếu công thức rnd() chỉ lấy từ phần tử k+1 trở xuống, thì mới không trùng.

Nghĩa là thay câu:


index = Int(Rnd() * (c - d + 1)) + d
bằng

index = Int(Rnd() * (c - k + 1)) + k

thêm bớt 1 theo lbound gì đó thành:

index = Int(Rnd() * (c - (k - Lbound(original) + 1) + 1)) + k - Lbound(original) + 1
 
Không biết tôi có làm sai chỗ nào.

Đương nhiên là sai rồi ---> Đầu tiên phải lấy ngẫu nhiên không trùng cho vào 1 biến array trước, xong mới for.. next theo biến array này
Tuy nhiên, nếu là tôi thì tôi sẽ sửa lại 1 chút cho phù hợp với CSDL trên Excel (mảng 2 chiều)
PHP:
Function Draw(Arr, Amount As Long)
  Dim index As Long, k As Long, d As Long, c As Long, tmpArr, original
  If Amount > UBound(Arr) - LBound(Arr) + 1 Then Exit Function
  original = Arr
  ReDim tmpArr(1 To Amount, 1 To 1)
  d = LBound(original)
  c = UBound(original)
  Randomize
  For k = 1 To Amount
    index = Int(Rnd() * (c - d - k + 2)) + d + k - 1
    tmpArr(k, 1) = original(index)
    original(index) = original(k + LBound(original) - 1)
    d = d + 1
  Next k
  Draw = tmpArr
End Function
PHP:
Sub Test1()
  Dim sArr(), Amount As Long, rArr
  sArr = Array(1, 2, 3, 4, 5, 9)
  Amount = 3
  rArr = Draw(sArr, Amount)
  Range("B1").Resize(Amount).Value = rArr
End Sub
------------------
Thuật toán của siwtom tôi hiểu lờ mờ rằng:
Là vầy sư phụ à:
- Ta có mảng Arr
- Duyệt từ 1 đến Amount
- Dùng Rnd để tính vị trí k
- Lấy phần từ thứ k của Arr cho vào mảng khác
- Lấy phần từ thứ nhất của Arr thế vào phần tử thứ k
===> Đó là lần quét đầu tiên
- Đến lần quét thứ 2 sẽ lấy phần tử thứ hai của Ar thế vào phần tử thứ k
vân vân...
Và chắc chắn 100% sẽ không có chuyện trùng, ngoại trừ trường hợp mảng Arr có trùng
 
Lần chỉnh sửa cuối:
Thay sub trên thành

PHP:
Sub Test1()
Dim sArr(), tArr(), i&, iSo&
sArr = Array(1, 2, 3, 4, 5, 9)
iSo = 3
tArr = Draw(sArr, iSo)
For i = 1 To iSo
  Cells(i, 2) = tArr(i)
Next i
End Sub

Tại sao thế thì tôi không biết, nhưng làm theo bài thì phải vậy
Hiểu rồi, phải lấy hết kết quả mới gán. Tôi thì khi gán nó chạy UDF => trùng là đương nhiên.
Cám ơn nhiều.
 
Web KT
Back
Top Bottom