Re: [討論]如何產生0與1組成的矩陣的排列組合

看板MATLAB作者profyang (prof)時間11年前 (2014/07/20 14:23)推噓1(1推 0噓 3→)

留言4則, 2人參與討論串2/2 (看更多)

: 推 jatj:http://goo.gl/QHWeyh exactly what you need 07/16 09:05 : 噓 jatj:為何不稍微回一下有沒有用呢？ 07/18 12:48 : → kurt28:推樓上原PO至少也回應一下吧 07/18 22:13 : j大您好，您提供的資料非常有用，非常抱歉這麼晚才回覆您， : 因為當時還有另一個問題想說能不能用您提供的資料來解決， : 這樣就不用上來再問一遍了， : 沒有及時回覆您在這裡跟您說聲抱歉， : 這邊還有另一個問題想再請教版上的各位， : 假設有一個1Xn的矩陣， : 矩陣內的元素可重複且相加要等於K， : 並得出所有的組合 : : 例如: : n=5 : K=10 : A=[a1 a2 a3 a4 a5] : a1+a2+a3+a4+a5=10 : : 一開始我的想法是先跑出所有可能的組合數， : 再利用if判斷來挑出符合的矩陣， : 因為我的寫法會把 : [1 1 1 1 1 ] : [2 2 2 2 2 ] : ... : [10 10 10 10 10 ] : 這幾種可能都跑過， : 所以當n與K很大時， : 處理時間便會非常久， : 且有可能會out memory， : 所以想請問版上的各位是否有其他的方法能解決， : 謝謝 : ※ 編輯: mann0614 (49.213.228.38), 07/19/2014 00:56:44 : 推 profyang:是只能正整數嗎? 我覺得這不容易就算有方法可以直接找出 07/19 15:16 : → profyang:你要的解,他的個數大約也是你全部可能點數的一半吧 07/19 15:17 : → profyang:也就是你現在全部可能列出來會爆就算有方法找出你要的解 07/19 15:17 : → profyang:也有可能會爆 07/19 15:18 : 推 kurt28:有回應有推! 07/19 21:27 : → mann0614:是正整數沒錯!那p大可以講一下您的寫法嗎？說不定能夠對 07/20 10:31 : → mann0614:我有幫助，目前我的寫法只能用於固定的n，若n改變就必須 07/20 10:31 : → mann0614:手動改變code，希望目前至少能夠進展到輸入任意數n時也 07/20 10:31 : → mann0614:能夠跑的程度，謝謝 07/20 10:31 : 推 profyang:不好意思昨天晚上頭腦不太清楚請忽略我上面的推文XD 07/20 13:30 : → profyang:你這基本上就是個重複組合的問題H(n,k)=C(n+k-1,k) 07/20 13:33 : → profyang:重複組合簡單介紹: http://0rz.tw/HRcK7 07/20 13:34 : 推 profyang:所以你要做的只是用nchoosek這個function把所有組合列出 07/20 13:36 : → profyang:來就對了當然你n和k太大而切n很接近k的話還是很可能爆掉 07/20 13:37 : → profyang:就是了 07/20 13:37 : → profyang: 且 07/20 13:37 簡單回一下大概像這樣: n=5; k=10; b=nchoosek(k-1,n-1); %所有正整數組合數 v=1:(k-1); C=nchoosek(v,n-1); %Matlab列出所有C(k-1,n-1)的可能排列 C=[zeros(b,1),C,k*ones(b,1)]; %開始轉成你要的正整數組合 D=diff(C,1,2); %所有可能 E=sum(D,2); %檢驗是否正確注意因為你要取的是正整數而一般重複排列用在這種相加是定值的是求非負整數所以你要想成(a1-1)+(a2-1)+(a3-1)+(a4-1)+(a5-1)=10-5 也就是實際組合數會變成C(n+(k-n)-1,n-1)=C(k-1,n-1) 最後再加回去實際上也不用特地加回去像我這樣用diff就好最後再檢驗一下正不正確 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.178.106 ※ 文章網址: http://www.ptt.cc/bbs/MATLAB/M.1405837415.A.D92.html