如何处理这样的组合问题

re-us

问题如下:
A=randn(100,1); 想求出这100个数里面任意挑选3个的平均值。
用nchoosek可以算出来总共有多少个组合，但是怎么求任意3个的平均值呢？非要用循环吗？

A=rand(100,1); max=0;

for i=1:100-2, for j=i+1:100-1,  for k=j+1:100

     ave=(A(i)+A(j)+A(k))/3;

     if ave>max, max=ave; end

end; end; end

事实上我要处理的数据远远不是100，一般是10的8次方的量级。在我的机器上这样循环至少得3天的时间，我想能不能先把这些组合用什么命令产生好，然后y用mean求出平均值，挑选出最大的，这样就不用循环了？有这样的命令吗？ 谢谢

[ 本帖最后由 ChaChing 于 2010-2-3 09:51 编辑 ]

sugarcane

看你的代码
难道max不就是100个数里最大的三个数的平均数么？
如果是的话，还好不是1000000000000000000000000000个数里挑50000000000000000000
个数。那你得算多少年:lol

re-us

那个循环就是算出来最大的平均值
我的意思是同样的功能，能不能不用循环？
就是这个东西特别费时间，应该有更好的算法。
谢谢你

花如月

下边的程序可以完成你要的功能

1. clear,clc, tic
   
2. len=100; D=rand(len,1);
   
3. N=nchoosek(len,3); L=N*3/len; A=cell(1,L);
   
4. for k=1:L,  A{k}=randperm(len); end
   
5. B=cell2mat(A);B=D(B);
   
6. result=blkproc(B,[1,3],@mean);
   
7. plot(result(1:100)); toc

复制代码

Elapsed time is 22.128757 seconds.
矩阵大速度确实比较慢，暂时没有什么好的办法解决。只是告诉你实现的思路，实际你只是为了看均值的走势。没必要列出所有的组合，len也没必要取到100。反正都是随机取值，结果影响不不会太大

[ 本帖最后由 ChaChing 于 2010-2-3 13:31 编辑 ]

re-us

非常谢谢 花如月
学到不少东西，上面的那段代码，解决了我其中一个问题。再次感谢

但是，可能我没有说清楚问题，对不起。
我必须要知道任意组合的那个三数字，一方面我要挑选最大平均值的那个组合，另一方面我要把所有组合的3个数作为方程系数，所以必须知道任意一个组合的3个具体数字。

实际上我的数据不是随机排列的，只是为了说明问题。我的数据如下：
a=[32.3,31.1,32.3,31.4,32.5,31.3,30.6,32.3,31.6,32.8,32.9,32.4,...
32.3,32.0,30.8,31.5,32.0,31.0,31.8,31.9,31.2,32.4,33.6,31.9,31.9,...
31.9,32.8,33.3,32.3,30.7,10.1,9.7,9.4,8.1,9.9,9.1,10.8,9.8,7.1,10.1,...
10.0,9.5,10.5,9.7,9.0,10.6,8.6,9.8,9.4,10.0,7.7,10.3,9.6,10.3,8.1,8.1,...
10.9,10.4,9.6,9.9,32.6,31.5,31.1,32.1,32.5,30.8,32.3,31.6,30.0,32.8,31.9,...
31.0,31.3,31.9,30.7,32.7,29.9,29.9,29.4,33.7,31.1,32.5,31.8,31.4,32.4,...
28.8,31.5,31.0,32.0,31.3,2.7,5.9,3.4,4.7,3.8,5.3,5.0,4.3,5.7,3.6];


非常谢谢

[ 本帖最后由 re-us 于 2007-12-8 16:07 编辑 ]

花如月

只需要把原来的rand(100,1)换成你的数组就可以了，如果不知道每次运算的数怎么得到运算结果呢？

有了结果想求个最大值有困难么？那段程序基本上可以解决你的问题，自己再多想想吧

[ 本帖最后由 ChaChing 于 2010-2-3 13:34 编辑 ]

re-us

非常感谢，我研究了1个小时，水平真高。
对，这段代码是可以实现我的功能。但是 花如月 可不可以稍微解释一下呢。对于核心的代码我还有点迷惑：

以D=[1 2 5];为例子，从3个里面选取2个，求平均

1. 我知道下面这几行是求出对应组合的脚标，但是不明白为什么要产生L个小的cell？感觉应该是产生L＝nchoosek（3，2）个小的cell，每个cell里面放2个脚标。
L=N*2/len;
A=cell(1,L);
for k=1:L
    A{k}=randperm(len);
end
B=cell2mat(A);
我知道这样作是对的，但是不知道为什么？

2. 如果我要求排列，那麽是不是 A{k}=randperm(len);要换成别的命令呢？

非常感谢 花如月，希望继续得到你的指导

花如月

第一个问题：L个cell每个cell函数长度为len的数据，那么数据的总长度就是L*len=N*每次取的个数
好像没有什么难理解的地方，就是为了保证产生的数据正好可以取N次要求的长度。

第二个问题：randperm只是为了产生随机的角标，达到随机取数的目的。

要具体问题具体分析，B=cell2mat(A);B=D(B);这里的B就是从100个随机数中任意取出3个的全排

re-us

首先非常感谢 如花月
我有一点还是不懂。 仍然以下面的代码为例子：
clear,clc
tic
len=3;
D=[1 2 5];
N=nchoosek(len,2);
L=N*2/len;
A=cell(1,L);
for k=1:L
    A{k}=randperm(len);
end
B=cell2mat(A);
C=D(B);
result=blkproc(C,[1,2],@mean);
就是说要调用2次（L＝2)randperm，randperm的说明是：
RANDPERM(n) is a random permutation of the integers from 1 to n.
我想理论是很有可能出现（虽然我试验了很多次，都没有出现）
A｛1，1｝＝1，2，3
A｛1，2｝＝3，2，1
那麽B＝1，2，3，3,2，1
很明显这样就错了。难道不可能出现这种情况吗？
再次感谢

花如月

那个只是近似，搜索后发现对于组合问题有更简单有效的方法。

1. tic
   
2. len=100;
   
3. D=rand(len,1);
   
4. A=combntns(D,3);
   
5. result=mean(A,2);
   
6. plot(result(1:100));
   
7. toc

复制代码

Elapsed time is 2.966273 seconds.
---------------------------------------------------------------------------------------------------------
    NCHOOSEK(V,K) where V is a vector of length N, produces a matrix
    with N!/K!(N-K)! rows and K columns. Each row of the result has K of
    the elements in the vector V. This syntax is only practical for
    situations where N is less than about 15.
--------------------------------------------------------------------------------------------------------
单单一个combntns就可以解决你的问题。因此在做编程的时候最好先搞清楚相关的函数功能以及用法。希望楼主再次使用函数的时候看全帮助文档。免得费这么大的周折，先入为主搞得我也以为没有现成的函数。后来搜索后发现不仅有而且不止一个（包括楼主提到的nchoosek），希望其他版友也能引以为鉴！

[ 本帖最后由 花如月 于 2007-12-10 14:13 编辑 ]

re-us

谢谢花如月

关键的问题是我怎么就搜索不到combntns:'(
说一下方法吧

花如月

原帖由 re-us 于 2007-12-11 10:08 发表

                               
登录/注册后可看大图

谢谢花如月

关键的问题是我怎么就搜索不到combntns:'(
说一下方法吧

百度，google应该也可以

[ 本帖最后由 花如月 于 2007-12-11 10:19 编辑 ]

eight

原帖由 re-us 于 2007-12-11 10:08 发表

                               
登录/注册后可看大图

谢谢花如月

关键的问题是我怎么就搜索不到combntns:'(
说一下方法吧

有可能你的matlab版本太低，所以没有这个函数

花如月

如果是matlab里边没有，那就是版本的问题。

可以把combntns换成nchoosek，程序也可以照常运行。

帮助里只是不推荐使用，但是结果好像相差不多。实在不行就换版本