Re: [讨论]如何产生0与1组成的矩阵的排列组合

楼主: profyang (prof)   2014-07-20 14:23:21
: 推 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就好
最后再检验一下正不正确
作者: mann0614 (逼哩叭啦)   2014-07-22 00:05:00
感谢p大您特地回文,解决了我的问题,也让我多学了一种写法,谢谢!
楼主: profyang (prof)   2014-07-22 01:56:00
不会,不过H(n,k)的成长还是很快XD 应该k=100 n=50之类的就会爆了吧~除非你电脑RAM爆大

Links booklink

Contact Us: admin [ a t ] ucptt.com