相乘 算法

jason680

回复 19# Windows19

$ echo 200 4 | awk '{t=1;a=$1;for(n=1;n<=$2;n+=1){t*=a*n};print $2"个文档, 文档="a"行, 结果="t"行";for(n=3;n<=10;n+=2){print "\n文档字符串，每行平均以"n"个来算\nx..xy..yz...zw...w + [回車] => 1行"n*4+1"个字符";print t"行=> "t*(n*4+1)/(1024^3)"GB"} }'
4个文档, 文档=200行, 结果=38400000000行

文档字符串，每行平均以3个来算
x..xy..yz...zw...w + [回車] => 1行13个字符
38400000000行=> 464.916GB

文档字符串，每行平均以5个来算
x..xy..yz...zw...w + [回車] => 1行21个字符
38400000000行=> 751.019GB

文档字符串，每行平均以7个来算
x..xy..yz...zw...w + [回車] => 1行29个字符
38400000000行=> 1037.12GB

文档字符串，每行平均以9个来算
x..xy..yz...zw...w + [回車] => 1行37个字符
38400000000行=> 1323.22GB

回帖到此...

xdsnet

排列、组合问题？
此外这个是否输入数据已经去重？输出是否需要去重？

如果行数太多（你所谓的上千行），这个计算机肯定会爆掉的。
就是不重复的情况，如果是取3行，有A(N,3)=N!/((N-3)!)，假设有500行，就有500*499*498可能，而且你每一行的字符数还不定，所以存储空间也是惊人的。

Windows19

回复 22# xdsnet

数据肯定没重复的 已处理过  再说行数可以取小一点
不淡大小  只谈实现

Windows19

回复 21# jason680

谢谢解释

xdsnet

如果已经去重，且知道行数，其实有一个很取巧的方法可以很快的得出结果，而且有重复的甚至比没有重复的更快。 这需要用到一个数学知识了 假设有N行（相互不重复，对应0,1,2，...,N-1 的序号），则取M个，每行可以重复时，就是有N*N..N（M个N相乘），所以如果有M段数字Z，每段有K种可能（K>=N)，则这个整体的0到Z的最大值 间的各个数字可以映射为取值可能，因为K可以用二进制表示，所以可以转换为K(n)，其中n是K对应的二进制位数，所以内容转换为有nM位的二进制数，可以分成M段，每段有n位，其对应的符合条件的数k（k<=N）就是符合条件的行序号。 这样依次增加输出数字（判断分段数值是否符合范围），就可以查出对应的重复行的可能，增加条件保证每段不重复就可以输出 不重复的可能。

这个算法的优点是O(n)复杂度的了。

不过这个算法实现可能需要用到大整数 位运算，不知道你好不好实现。 比如，有8行，要取3行，因为N=8,对应n=3，M=3，所以需要一个9位二进制数表示可能（重复时刚好全覆盖）

1. // 伪C语言 逻辑实现
   
2. for(i=0;i<1024;i++){
   
3.      line1= (i>>(3*0)) & 0x7;
   
4.      line2= (i>>(3*1)) & 0x7;
   
5.      line3= (i>>(3*2)) & 0x7;
   
6. 
   
7.      // 如果扩展，这里line等可能需要用数组存储， 1024要换成n*M+1位二进制数， 0x7要换成对应n的n位1二进制数，3换成n对应数字，0,1,2等其实是和M相关的，后面就可以用到循环中
   
8.      // 例如 for(j=0;j<M;j++){
   
9.     //       line[j]=(i>>(3*j)) & 0x7;
   
10.     //  }
    
11. 
    
12.      // 这里根据 line1，line2，line3 输出可重复的结果
    
13.      if(line1==line2 || line1== line3 || line2==line3){ // 这里过滤重复情况
    
14.           continue
    
15.      }
    
16.      //  这里根据 line1，line2，line3 输出不重复的结果
    
17. }

复制代码