作者chris70211 (克里斯)
看板C_Sharp
標題[問題] 如何有效找出所有可能性組合
時間Tue Jul 16 21:47:15 2013
目前因為程式上需求 需要寫一個能夠找出一陣列內所有相加後可能的值
例如：一陣列內容有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
2F：推 qwer820404:你這樣列出來之後 你可以去觀察一下 其實有個特性在 07/17 01:32
3F：推 qwer820404:我會先對陣列做排序，排完後會有個特性 每個組合的後數 07/17 07:56
4F：→ qwer820404:一定大於他前數 (在於陣列值不會有重複出現的情況下) 07/17 07:57
5F：→ qwer820404:那如果說 值有可能重覆 那要的組合方式有二種情況 07/17 07:58
6F：→ qwer820404:重覆的值 在一個組合裡只會出現一次 也就是說 出現一個 07/17 07:59
7F：→ qwer820404:跟出現100個同樣的值 還是等同於出現一次 就可以先用 07/17 07:59
8F：→ qwer820404:就可以先 消除掉不必要的 只留下最後確定有用的再處理 07/17 08:00
9F：→ qwer820404:那如果重覆的值 可以出現多次 就代表說 可以用個技巧 07/17 08:01
10F：→ qwer820404:讓程式 會把一樣的值 當作都是不一樣的東西 07/17 08:01
11F：→ qwer820404:那如果這種要用遞迴做 後數會是大於等於他前數 07/17 08:02
12F：→ qwer820404:如果小弟的做法有什麼可改或思考有不對的 歡迎指教 07/17 08:03
可能一開始規則沒訂好 假設我的矩陣目前有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)
13F：推 qwer820404:我得比較不同耶 我是在做組合前就先考量重覆性定義 07/17 23:50
14F：→ qwer820404:你是在組合後 才去做 所以 你的COST會比較高吧 07/17 23:50
15F：→ StupidGaGa:這問題像學校出的，考基礎邏輯概念 07/18 10:24
16F：→ StupidGaGa:如果要考慮到程式的彈性 建議這問題切割成許多function 07/18 10:26
17F：→ StupidGaGa:1.先做n相異物不重複取出m組合，先簡稱Cnm 07/18 10:29
18F：→ StupidGaGa:2. 把n跟m變化 07/18 10:30
19F：→ StupidGaGa:兩個大Function概念是這樣 07/18 10:31
因為重點在於矩陣數值的相加的值
所以如果在相加之前就考慮重覆性會把相加的可能性降低
例如 1 2 2
相加的值就會有1 2 2 3 3 4 5
可是如果一開始就考慮重覆性的問題
相加的值就只會有 1 2 3不知道有沒有誤解你們的意思
※ 編輯: chris70211 來自: 114.38.122.29 (07/18 21:03)
20F：→ qwer820404:有…你還是在以結果面來看 結果都是一樣的 07/19 00:09
21F：→ qwer820404:是做法上跟順序不同 同樣的結果 不一樣的過程 07/19 00:10
22F：→ qwer820404:重覆不重覆是你的情境下設定的條件啊 07/19 00:10
23F：→ StupidGaGa:數值重複這本來就要等到全部做完才知道 07/19 02:10
24F：→ StupidGaGa:你先考慮數值重複在思考排列是本末倒置的做法 07/19 02:10
25F：→ StupidGaGa:有時候問題不只一種解法，要找適合你自己的解法 07/19 02:11
26F：→ StupidGaGa:不過可以確定的是，你那寫法不太優.... 07/19 02:19
27F：→ StupidGaGa:如果你是學生，我認為你就照你的想法寫沒差 07/19 02:20
28F：→ StupidGaGa:如果在工作，你那樣寫法程式彈性不夠，後人維護困難 07/19 02:21
29F：推 hangchu:這叫幕集合(power set)，我在 Programming 版有發問過 07/20 03:03