PTT數位生活區 / C_Sharp (C#)

[問題] 如何有效找出所有可能性組合

看板C_Sharp (C#)作者 (克里斯)時間12年前 (2013/07/16 21:47), 編輯推噓4(4推 0噓 26→)
留言30則, 4人參與, 最新討論串1/1
目前因為程式上需求 需要寫一個能夠找出一陣列內所有相加後可能的值 例如：一陣列內容有1 2 3 4 5 那可能會產生的值就會有 1 2 3 4 5 1+2 1+3 1+4 1+5 2+3 2+4 2+5 3+4 3+5 4+5 1+2+3 1+2+4 1+2+5 1+3+4 1+3+5 1+4+5 2+3+4 2+3+5 3+4+5 1+2+3+4 1+2+3+5 2+3+4+5 1+2+3+4+5 不知道大家有沒有碰過相關的問題 不知道統計或是數學上有沒有這種的公式可以使用的 還在努力想有什麼相關聯>"< -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.38.122.183
→
07/16 23:54, , 1F
可參考這篇文章 http://ppt.cc/eeai
07/16 23:54, 1F
推
07/17 01:32, , 2F
你這樣列出來之後 你可以去觀察一下 其實有個特性在
07/17 01:32, 2F
推
07/17 07:56, , 3F
我會先對陣列做排序，排完後會有個特性 每個組合的後數
07/17 07:56, 3F
→
07/17 07:57, , 4F
一定大於他前數 (在於陣列值不會有重複出現的情況下)
07/17 07:57, 4F
→
07/17 07:58, , 5F
那如果說 值有可能重覆 那要的組合方式有二種情況
07/17 07:58, 5F
→
07/17 07:59, , 6F
重覆的值 在一個組合裡只會出現一次 也就是說 出現一個
07/17 07:59, 6F
→
07/17 07:59, , 7F
跟出現100個同樣的值 還是等同於出現一次 就可以先用
07/17 07:59, 7F
→
07/17 08:00, , 8F
就可以先 消除掉不必要的 只留下最後確定有用的再處理
07/17 08:00, 8F
→
07/17 08:01, , 9F
那如果重覆的值 可以出現多次 就代表說 可以用個技巧
07/17 08:01, 9F
→
07/17 08:01, , 10F
讓程式 會把一樣的值 當作都是不一樣的東西
07/17 08:01, 10F
→
07/17 08:02, , 11F
那如果這種要用遞迴做 後數會是大於等於他前數
07/17 08:02, 11F
→
07/17 08:03, , 12F
如果小弟的做法有什麼可改或思考有不對的 歡迎指教
07/17 08:03, 12F
可能一開始規則沒訂好 假設我的矩陣目前有15個值 1 2 3 3 4 4 5 6 7 7 8 9 10 11 12 然後要根據這十五個值排出其相加所有能夠產生的值 例如1+2 +3+3+4=13 所以一樓的那個做法可能就沒辦法了QQ 目前用比較笨的方法 假設我的陣列B1=[1 2 2 3 4] 5個值我就設五層的FOR迴圈 然後用一個ArrayList用放所以可能產生的值 for i=0;i<5i++ { A1.Add(B1[i]); for j=2:5 (簡寫) if (j>i) { A1.Add(B1[i]+B1[j]); for k=3:5 { if (k>j) { A1.Add(B1[i}+B1[j]+B1[k]); for L=4:5 { if(L>k) { A1.Add(B1[i]+B1[j]+B1[k]+B1[L]); for (M=5;M<=5;M++) { if(K>M) { A1.Add(B1[i]+B1[j]+B1[k]+B1[L]+B1[M]); }}}}}}}} 這樣的做法就能夠把所有可能產生的值列出來 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 1+2+3+5 1+2+4 1+2+4+5 1+2+5 1+3 . . . 這樣的做法成找出所以相加的可能性 之後再將A1用兩個迴圈去判定有沒有重覆的 重複的就移除囉!! 不過除了這樣的方法有沒有什麼更好的方法 不知道2樓的大大是不是跟我一樣的意思 因為這個方法還滿耗時間的 而且算是暴力破解法吧(汗) 希望大家一起討論看看囉!! ※ 編輯: chris70211 來自: 114.38.119.227 (07/17 22:23)
推
07/17 23:50, , 13F
我得比較不同耶 我是在做組合前就先考量重覆性定義
07/17 23:50, 13F
→
07/17 23:50, , 14F
你是在組合後 才去做 所以 你的COST會比較高吧
07/17 23:50, 14F
→
07/18 10:24, , 15F
這問題像學校出的，考基礎邏輯概念
07/18 10:24, 15F
→
07/18 10:26, , 16F
如果要考慮到程式的彈性 建議這問題切割成許多function
07/18 10:26, 16F
→
07/18 10:29, , 17F
1.先做n相異物不重複取出m組合，先簡稱Cnm
07/18 10:29, 17F
→
07/18 10:30, , 18F
2. 把n跟m變化
07/18 10:30, 18F
→
07/18 10:31, , 19F
兩個大Function概念是這樣
07/18 10:31, 19F
因為重點在於矩陣數值的相加的值 所以如果在相加之前就考慮重覆性會把相加的可能性降低 例如 1 2 2 相加的值就會有1 2 2 3 3 4 5 可是如果一開始就考慮重覆性的問題 相加的值就只會有 1 2 3不知道有沒有誤解你們的意思 ※ 編輯: chris70211 來自: 114.38.122.29 (07/18 21:03)
→
07/19 00:09, , 20F
有…你還是在以結果面來看 結果都是一樣的
07/19 00:09, 20F
→
07/19 00:10, , 21F
是做法上跟順序不同 同樣的結果 不一樣的過程
07/19 00:10, 21F
→
07/19 00:10, , 22F
重覆不重覆是你的情境下設定的條件啊
07/19 00:10, 22F
→
07/19 02:10, , 23F
數值重複這本來就要等到全部做完才知道
07/19 02:10, 23F
→
07/19 02:10, , 24F
你先考慮數值重複在思考排列是本末倒置的做法
07/19 02:10, 24F
→
07/19 02:11, , 25F
有時候問題不只一種解法，要找適合你自己的解法
07/19 02:11, 25F
→
07/19 02:19, , 26F
不過可以確定的是，你那寫法不太優....
07/19 02:19, 26F
→
07/19 02:20, , 27F
如果你是學生，我認為你就照你的想法寫沒差
07/19 02:20, 27F
→
07/19 02:21, , 28F
如果在工作，你那樣寫法程式彈性不夠，後人維護困難
07/19 02:21, 28F
推
07/20 03:03, , 29F
這叫幕集合(power set)，我在 Programming 版有發問過
07/20 03:03, 29F
→
07/20 03:03, , 30F
07/20 03:03, 30F
‣ 更多 chris70211 的文章
文章代碼(AID): #1HvKxcLw (C_Sharp)
C_Sharp 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 chris70211 的文章
文章代碼(AID): #1HvKxcLw (C_Sharp)