頁:
[1]
c++ 分組 重複率最低
我想用c++寫一個自動分組的程式,但分組名單重複率要最低,EX: 30人分六組第一次:隨機分組
第二次:第一次沒有分到的盡量分在一組,第一次有分到的盡量不要分在一組(一樣的人)
以此類推~第三次 第四次 第五次 第六次,讓每次分組的人彼此重複最少次。
有沒有甚麼公式可以用
我是想到的是有在一起過的加一分,例如:有六個人A B C D E F分2組
第一次:
第一組 A B C
第二組 D E F
表格: A B C D E F
A X 1 1 0 0 0
B 1 X 1 0 0 0
C 1 1 X 0 0 0
D 0 0 0 X 1 1
E 0 0 0 1 X 1
F 0 0 0 1 1 X
第二次:
根據上面的表格找出最小的數字和
第一組 D B C 0+0+0+1+1+0=2
前兩個臨零是D和B,C沒被分到所以是0,再來B和D C所以是0 1 再來 C 和 B D 所以是 1 0
第二組 A E F 0+0+0+1+1+0=2
表格: A B C D E F
A X 1 1 0 1 1
B 1 X 2 1 0 0
C 1 2 X 1 0 0
D 0 1 1 X 1 1
E 1 0 0 1 X 2
F 1 0 0 1 2 X
以此類推算組合最小的數 2+2=4 最小所以重複率最小
,因為這人數少所以可以全部組合算出來後再去比較,
但如果有30人分六組共有150萬多組,不太可能全部算出來在比較吧!
就算是電腦也要算很久,所以有沒有甚麼公式或方法過濾這些組合,
找出最好的分組阿
感謝
...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 如果只是要延伸你的邏輯到 30 人 6 組或更大, 其實很簡單也很快
因為它屬於 greedy algorithm, 每個步驟都做出當下最佳的選擇
出來的結果絕大部份情況下都不差
真正的問題在於你需不需要和怎麼證明這邏輯分配出來的一定是 "重覆率最小"
換句話說你可以用 greedy algorithm, 或者一定要 search 不知道有沒有誤會你的意思,
應該是只要將「第一次:隨機分組」時,被分在同一組的人於第二次分組時平均分散就可以了 本帖最後由 gitlab 於 2016-7-8 03:53 AM 編輯
你可能要先定義一下什麼是"重覆率" 和 "彼此重複"
例如
1. ABC, DEF
2. DBC, AEF
這兩次分組的"重覆率"為何?
1. ABC, DEF
2. DBC, AEF
3. DBE, ACF
這三分組的"重覆率" 又是?
a333221 發表於 2016-7-5 11:27 PM static/image/common/back.gif
不知道有沒有誤會你的意思,
應該是只要將「第一次:隨機分組」時,被分在同一組的人於第二次分組時平均分 ...
對沒錯 盡量別讓在一起過一組的人在同一組 謝謝<br><br><br><br><br><div></div> gitlab 發表於 2016-7-8 03:51 AM static/image/common/back.gif
你可能要先定義一下什麼是"重覆率" 和 "彼此重複"
例如
B和C重複在同一組2次
A和C重複在同一組2次
D和E重複在同一組2次
E和C重複在同一組2次
以此類推~
盡量讓重複在重複在同一組的次數最小
謝謝
頁:
[1]