本来是想在网上搜索下现成的,结果看到一堆想吐的,尼玛啊,什么递归了,什么回溯了。无语!难道就不能负责任点,搜索下相关算法,然后,好好的实现下?又不是有多难的算法!最可恶的是,这些人还zhuangbility,以为自己写的算法很好,贴出来炫耀,有啥可炫耀的?
数学简单道理
N! <<<< N^N
我把它看成N进制,全部生成一遍,去掉位数有重复的,必然是N!这样的排列算法都比哪些瞎写的好
C(N,K> <<< N^K,同样用N进制,一共K位,那样全生成一遍,去掉不合理的(如必须是升序,或者降序),自然是对的。就这个最浅显的算法,也比这些zhuangbility的人贴的算法强。
给个knuth排列组合书(第四卷)的算法实现(这还是其性能最差的一个)
//在N中选取K个数,[first,last)必须有序 template<typename rand_it,typename T> void choose(rand_it first,rand_it last,int k,std::vector<std::vector<T> >&out) { std::vector<int> assitVec ; assitVec.resize(k+1); //std::sort(vec.begin(),vec.end()); //<1>初始化,//需要增加一个哨兵 //std::copy(vec.begin(),vec.begin()+k,assitVec.begin()); assitVec.resize(k+1); for(int j=0;j<k+1;j++){ assitVec[j]=j; } int N=std::distance(first,last); int bit=0; int i=0; assitVec[k]=N; LOOP: //<2>判断终止条件 if(assitVec[i] == N){ //结束 return ; } //<3>输出辅助数组 out.push_back(std::vector<T>(k)); for(int j=0;j<k;j++) { rand_it it = first; std::advance(it,assitVec[j]); out.back()[j] = *it; } //<4>调整 int flag=0; while(i<k){ if(assitVec[i] +1 == assitVec[i+1]) { //需要进一位,当前位恢复原始状态 assitVec[i] = i; i++; flag=1; } else{ assitVec[i]++; break; } } if(assitVec[i] == N){ //结束 return ; } for(bit=0;bit<i;bit++){ assitVec[bit]=bit; } if(flag){ i=0; } goto LOOP; }
上面的迭代器,虽然写的是random_it,但实际上支持output_it就可以了。
仅仅是 std::advance(it,assitVec[j]);这句稍微慢一点,当然实际上可以忽略。
使用如下举例:前提条件 K要小于集合长度
int main(int argc,char*argv[]){ std::vector<int>vec(10); for(int i=0;i<10;i++){ vec[i]='z'-i; } std::vector<std::vector<int> > out; // std::sort(vec.begin(),vec.end()); choose(vec.begin(),vec.end(),3,out); printf("%d\n",out.size()); for(int i=0;i<out.size();i++){ for(int j=0;j<out[i].size();j++){ std::cout<<(char)out[i][j]<<","; } std::cout<<std::endl; } return 0; }
相关推荐
/k 将测试页打印到指定的打印机,不能安装打印机时的命令组合 /l[path] 打印机驱动程序源路径 /m[model] 打印机驱动程序型号名 /n[name] 打印机名 /o 显示打印机队列查看 /p 显示打印机属性 /q 安静模式,不...
11.二次剩余((ax+k)2≡n(modp)(ax+k)^2≡n(mod p)(ax+k) 2 ≡n(modp)) 12.十进制矩阵快速幂(n很大很大的时候) 13.欧拉函数 14.费马小定理 15.二阶常系数递推关系求解方法 (a_n=p*a_{n-1}+q*a_{n-2}) 16.高斯消元 ...
与这k个数的排列顺序无关,所以我们可以令a[I][I+1](a[I]表示第I个数在原数列中的位置),这个组合生成算法的复杂度大约为C(n,k),下面给出递归搜索算法的框架: Proc Search(dep) Begin for i [dep - 1] + 1 to ...
编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小(输出应包括所去掉的数字的位置和组成的新的正整数,N不超过240位)。 21、 对于下图给出的有向网,写出用Dijkstra方法求从顶点A到图中其它顶点的最短...
ls -lt 是“-l”和“-t”的组合,按时间顺序显示列表。 ls -F 显示文件类型,目录“/ ”结尾;可执行文件“*”结尾;文本文件(none),没有结尾。 ls -R 递归显示目录结构。即该目录下的文件和各个副目录下的文件...
∷相关函数:c函数 8 1.1.5 魔方阵 9 范例1-5 魔方阵 9 1.1.6 三维数组的表示 14 范例1-6 三维数组的表示 14 ∷相关函数:InitArray函数 1.1.7 多项式的数组表示 17 范例1-7 多项式数组的表示 17 1.1.8 查找...
如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论: ① 若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号...
-c:cancel current process取消目前正在执行的关机程序。所以这个选项当然没有时间参数,但是可以输入一个用来解释的讯息,而这信息将会送到每位使用者。 -F:在重启计算机时强迫fsck。 -time:设定关机前的...
∷相关函数:c函数 8 1.1.5 魔方阵 9 范例1-5 魔方阵 9 1.1.6 三维数组的表示 14 范例1-6 三维数组的表示 14 ∷相关函数:InitArray函数 1.1.7 多项式的数组表示 17 范例1-7 多项式数组的表示 17 1.1.8 查找...
用户可选择d m e ,然后if语句将作出判断,d表示执行标号为defrag的程序段,m表示执行标号为mem的程序段,e表示执行标号为end的程序段,每个程序段最后都以goto end将程序跳到end标号处,然后程序将显示good bye,...
matlab三维张量分解代码使用Intel ...++使用模板和Python生成(type(X),type(T))之间的所有组合 通过使用以下事实来支持张量:如果我们具有大小为D1..Dn和目标尺寸k的输入张量,则可以将问题简化为3维情况Da
作业平均周转时间=∑(作业完成时刻i-作业提交时刻i)/n个作业 (2)最短作业优先:在作业内容参差很不均衡时有合理性 (3)“响应比”最高的优先 “响应(系数)比”:作业响应时间(等待和运行)/...
具体使用帮助文件中写得非常详细,我就不再多说了 ——当然流光里附带的XKEY也是一个相当不错的字典生成程序。 3、流光其实不仅仅是一个在线安全检测工具——而是一个"工具包",同时具有以下几个辅助功能 A、...
(1)打开Visual Studio 2008 开发环境,新建一个Windows窗体应用程序,并将其命名为Encrypt。 (2)更改默认窗体Form1 的Name 属性为Frm_Main,在该窗体中添加两个GroupBox 容器控件,其中, 在第一个GroupBox 中放...
序)的软件组合。 在面向对象的程序设计中,你可以用软件对象表示现实世界的对象,而这些软件对象和 现实世界对象是相对应的。例如:如果你正在建立一个帐户管理系统,那么你的对象就是帐 户、欠款、信用卡、月收入...
LINGO生成了三个父集的所有组合共八组作为allowed集的成员。列表如下: 编号 成员 1 (A,M,1) 2 (A,M,2) 3 (A,N,1) 4 (A,N,2) 5 (B,M,1) 6 (B,M,2) 7 (B,N,1) 8 (B,N,2) 成员列表被忽略时,派生集成员由父集...
--hex* --bin 字库输出类型; --horiz-scan* --verti-scan 点阵字符扫描模式; --h-to-l* --l-to-h 点阵字符在字节的存储方式; --font-high=[font_h] 点阵字符的高与宽(应当相等)。 注:* 是默认项。 例子...
如果输出文件名没有指定,注释数据会被发送到标准输出设备。 例子: 1) rar cw oldarch comment.txt 2) rar cw -scuc arc unicode.txt 3) rar cw arc d 从压缩文件中删除文件。请注意,如果这个命令导致...
* 对于文本、声音、图像和 32 位和 64 位 Intel 可执行程序压缩的特殊优化算法 * 获得比类似工具更好的压缩率,使用'固实'压缩 * 身份校验(只有注册版本可用) * 自解压压缩文件和分卷压缩(SFX) * 对物理损伤的...