求助：matlab程序实现盒子放球的组合问题

xiangpan18

有m个相同的小球，任意放入n个不同的盒子内，其组合数为C（m+n-1，m），想得到各个组合，请各位大侠出手相助，多谢！！！

qibbxxt

你的给出一种放置方式的示例来，这样大家就有个目标了

qibbxxt

你给的公式是不是有点问题啊，请仔细检查一下

1. >> f  = @(m,n)unique(sort(fullfact(n + zeros(1,m)),2),'rows');
   
2. >> f(3,2)
   
3. ans =
   
4.      1     1     1
   
5.      1     1     2
   
6.      1     2     2
   
7.      2     2     2
   
8. >> f(3,4)
   
9. ans =
   
10.      1     1     1
    
11.      1     1     2
    
12.      1     1     3
    
13.      1     1     4
    
14.      1     2     2
    
15.      1     2     3
    
16.      1     2     4
    
17.      1     3     3
    
18.      1     3     4
    
19.      1     4     4
    
20.      2     2     2
    
21.      2     2     3
    
22.      2     2     4
    
23.      2     3     3
    
24.      2     3     4
    
25.      2     4     4
    
26.      3     3     3
    
27.      3     3     4
    
28.      3     4     4
    
29.      4     4     4

复制代码

一下是我算的结果

liuyalong008

1. function r=choose_box(m,n)
   
2. %% m=4,n=3
   
3. 
   
4. t=nchoosek(repmat(0:m,1,n-1),n);
   
5. c=t(sum(t,2)==m,:);
   
6. r=unique(cell2mat(arrayfun(@(i)sort(c(i,:)),(1:size(c,1))', 'UniformOutput' ,0)),'rows');
   
7. end

复制代码

1. >> f=choose_box(5,4)
   
2. 
   
3. f =
   
4. 
   
5.      0     0     0     5
   
6.      0     0     1     4
   
7.      0     0     2     3
   
8.      0     1     1     3
   
9.      0     1     2     2
   
10.      1     1     1     2
    
11. 
    
12. >> f=choose_box(4,5)
    
13. 
    
14. f =
    
15. 
    
16.      0     0     0     0     4
    
17.      0     0     0     1     3
    
18.      0     0     0     2     2
    
19.      0     0     1     1     2
    
20.      0     1     1     1     1

复制代码

liuyalong008

算法太慢，可行的解决方案是生成一个（x行n列）数组其每行相加等于m

xiangpan18

不好意思原帖子写错了，是相同小球放入不同盒子

xiangpan18

qibbxxt 发表于 2013-5-21 15:41
你给的公式是不是有点问题啊，请仔细检查一下一下是我算的结果

不好意思原来写错了，应该是相同的小球放入不同的盒子。举例：4个相同的小球放入3个不同的盒子，则
4,0,0;
3,1,0;
2,2,0;
1,3,0;
0,4,0;
0,3,1;
0,2,2;
0,1,3;
0,0,4;
1,0,3;
2,0,2;
3,0,1;
2,1,1；
1,2,1；
1,1,2;
共计C(4+3-1,4)=15种组合

bainhome

建议去仔细看3#的答案，你改完题目，祁工的做法仍然是对的。

lengyunfeng

xiangpan18 发表于 2013-5-21 19:54
不好意思原来写错了，应该是相同的小球放入不同的盒子。举例：4个相同的小球放入3个不同的盒子，则
4,0,0 ...

不对，4个一样的球放3个不同的盒子里应该有18种分法，公式是C（3,1）+C（3,1）*C（2,1）+C（3,1）*3＝3+3*2+3*3＝18种；因为球有4个球，那么至少有一个盒子里的球的个数>=2。这样，就有了上面的公式，第一项表示4个球都放在同一个盒子里，这时候有三种选择；第二项，表示3个球放一个盒子里，1个球放在剩下的两个盒子里，这时候应该有3*2＝6种选择；第三项，表示2个球放一个盒子里，剩下的2个球放在剩下的两个盒子里，这时候应该有3*3种选择，所以总共有18种情况。

lin2009

问题出处：
http://forum.simwe.com/thread-1079234-1-1.html
有m个相同的小球，任意放入n个不同的盒子内，其组合数为C(m+n-1,m)，欲得到所有盒子中球数。

题目应该蕴含一个前提条件：m > n, 且m个小球都要放完。
则组合数为 C（m+n-1，m）

这是典型的排列组合问题，公式是正确的。其实容易得出。说明如下：
在同一行上，画上n+m个方格子。这n+m个方格子将要分别表示小球和盒子。
将第一个方格标上“盒子”，再将n-1个“盒子”标志放在剩下的n+m-1个方格里。
其他格子（m个）格子均代表“小球”。
每个“盒子”后面直到下一个“盒子”为止（最后一个“盒子”直到最后一格为止）的“小球”标志的方格数就可以代表盒子里的小球的个数。
因此题目的要求的组合数就可以转化为 在n+m-1个格子里挑出 n-1个 格子表示盒子的组合问题，
即
C(m+n-1,n-1) = C(m+n-1,m)
要求每个“盒子”的“小球”个数，就数一数其后“小球”个数即可。在Matlab中可以用“盒子”所在位置相减的方法得出。

结合Matlab的排列组合函数就可得出各个组合的程序：

1. %%
   
2. % m个相同的小球，任意放入n个不同的盒子内，其组合数为C(m+n-1,m)，欲得到所有盒子中球数。
   
3. % 题目应该蕴含一个前提条件：m > n, 且m个小球都要放完。请核实。
   
4. 
   
5. m = 8; % 球数
   
6. n = 5; % 盒子数
   
7. 
   
8. Box_position_temp = nchoosek(1 : m+n - 1, n-1) + 1;  % 第一个格子的位置为基准, 标记为序号1.注意这是从第2个盒子到第n个盒子的位置矩阵.
   
9. Box_position_temp(:,end+1) = 1;                      % 目的有二：拓展矩阵，及插入第一个盒子的位置信息。                        
   
10. Box_position = circshift(Box_position_temp,[ 0, 1 ]);% 得到n个盒子的位置矩阵。
    
11. 
    
12. Post_position_temp = Box_position;                      % 后一个盒子位置的矩阵。
    
13. Post_position_temp = circshift(Box_position, [ 0, -1 ]);% 储存每一个盒子后面紧相连一个盒子的位置(从第1个开始）。左移操作。
    
14. Post_position_temp(:,end) = m+n+1;                      % 最后一个盒子的“虚拟的或假象的”后一个盒子的位置。在所有格子之外，即在虚拟的第m+n+1格。
    
15. Post_position = Post_position_temp;                     % 此句可以改写或省略，此处主要是便于阅读程序。
    
16. 
    
17. NumsBall_Box = Post_position - Box_position -1          % 得出每个盒子里的小球的个数.Well done.

复制代码

qibbxxt

xiangpan18 发表于 2013-5-21 19:54
不好意思原来写错了，应该是相同的小球放入不同的盒子。举例：4个相同的小球放入3个不同的盒子，则
4,0,0 ...

要得到lz的这种形式的结果，对上述代码进行改造即可

1. f = @(m,n)unique(sort(fullfact(n + zeros(1,m)),2),'rows')';
   
2. g = @(m,n,f)repmat(1:length(f(m,n)),m,1);
   
3. h = @(m,n)accumarray([reshape(f(m,n),[],1),reshape(g(m,n,f),[],1)],1);

复制代码

运行

1. >> h(4,3)
   
2. ans =
   
3.      4     3     3     2     2     2     1     1     1     1     0     0     0     0     0
   
4.      0     1     0     2     1     0     3     2     1     0     4     3     2     1     0
   
5.      0     0     1     0     1     2     0     1     2     3     0     1     2     3     4

复制代码

qibbxxt

qibbxxt 发表于 2013-5-22 09:12
要得到lz的这种形式的结果，对上述代码进行改造即可运行

再补充一种

1. f = @(m,n)histc(unique(sort(fullfact(n + zeros(1,m)),2),'rows')',1:n)

复制代码

测试

1. >> f(4,3)
   
2. ans =
   
3.      4     3     3     2     2     2     1     1     1     1     0     0     0     0     0
   
4.      0     1     0     2     1     0     3     2     1     0     4     3     2     1     0
   
5.      0     0     1     0     1     2     0     1     2     3     0     1     2     3     4

复制代码

qibbxxt

qibbxxt 发表于 2013-5-22 09:27
再补充一种测试

再来一种，枚举法的

1. m = 4;
   
2. n = 3;
   
3. f = unique(randi([0,m],1000,n),'rows');
   
4. f(sum(f,2)~=m,:)=[];

复制代码

bainhome

lin2009兄按问题本身忠实浮现解决方案，赞一个。
不过我更倾向于祁工3#的做法，后面加个hist就可以。
匿名函数循环套解的方式建议大家多用用。数值程序里很多复杂函数的描述，这种方式几乎是唯一的表述方法。

ps:写完才发现，祁工的histc已经发出来了，好快！！

xiangpan18

bainhome 发表于 2013-5-22 10:23
lin2009兄按问题本身忠实浮现解决方案，赞一个。
不过我更倾向于祁工3#的做法，后面加个hist就可以。
匿名 ...

您好！请问匿名函数和写成脚本文件的函数有什么区别和优势，速度更快么

bainhome

二者本质一样，但匿名函数构造出入口的思路更便捷，适合于变动参数条件下的动态构造，这在函数形式非常复杂时体现得尤其明显。例子由于一些原因我就不给了，见谅。
参照祁工和吴工论坛里的一些例子，会有体会，答案就在他们写的很多代码里。
arrayfun系列、操纵索引(我认为这是该函数最出效果的地方)的bsxfun函数，匿名机制、逻辑数组等方法的灵活组合，会给MATLAB做算法实现、尤其带复杂函数出入口的算法实现带来比较深刻的改变。——个人看法

rocwoods

xiangpan18 发表于 2013-5-23 07:57
您好！请问匿名函数和写成脚本文件的函数有什么区别和优势，速度更快么 ...

速度到不会快，但是当小函数很多时，并且函数中已知参数较多时，用匿名函数比写成脚本文件要简洁方便许多。

qibbxxt

xiangpan18 发表于 2013-5-23 07:57
您好！请问匿名函数和写成脚本文件的函数有什么区别和优势，速度更快么 ...

匿名函数在C#这个语言中也有，不过C#的匿名函数可以写多条语句
本人认为匿名函数的好处在于简洁，当小函数比较多的时候，给人一种杂乱的感觉
有些小函数可能只用到一两次，却要写个文件，所以从开发者的角度来说，比较简洁

从Matlab的体会来说，很多函数都支持函数句柄作为输入，因此直接构造匿名函数，用起来很舒服

nwcwww

qibbxxt 发表于 2013-5-22 09:47
再来一种，枚举法的

类似的思路，用到了统计工具箱里的fullfact：

1. m = 4;
   
2. n = 3;
   
3. f = fullfact(m+ones(n, 1))-1;
   
4. f(sum(f, 2) ~= m, :) = [];

复制代码