演示@google code
1-n 全排列问题
1.非递归解法
思路 :利用数字下标从小增到最大,同一字符编同一数字
12345->12354->12435->12453->.....
find a[i]>a[i+1] , find j ,j>i && j<n && a[j]>a[i] && a[j+1]<a[i] ,swap a[i].a[j] ,reverse a[i ~ n]
function perm(str){
var n=str.length;
var perm_start=[];
var start=1;
var charIndex={};
for(var i=0;i<n;i++){
if(i==str.indexOf(str[i])){
charIndex[str[i]]=start++;
}
perm_start.push(charIndex[str[i]]);
}
var perm_strs=[];
var over=false;
while(!over){
var tmpstr=[];
for(var i=0;i<perm_start.length;i++){
tmpstr.push(str[perm_start[i]-1]);
}
perm_strs.push(tmpstr);
over=true;
var i=n-1;
for(i=n-1;i>0;i--) {
if(perm_start[i]>perm_start[i-1]) {
over=false;
break;
}
}
if(!over){
var minIndex=i;
for(;minIndex<n;minIndex++) {
if(perm_start[minIndex] < perm_start[i-1]){
break;
}
}
minIndex--;
var t=perm_start[i-1];
perm_start[i-1]=perm_start[minIndex];
perm_start[minIndex]=t;
var right=perm_start.splice(i);
right.reverse();
perm_start=perm_start.concat(right);
}
}
return perm_strs;
}
2.递归解法
思路:两两交换,穷尽所有可能
#include <iostream>
#include <iomanip>
#include <functional>
using namespace std;
template <typename T>
void Perm(T* List, int k, int m) {
int i;
if (k == m) {
for (i = 0; i <= m; i++) {
std::cout << List[i];
}
std::cout << std::endl;
}
else {
for (i = k; i <= m; i++) {
std::swap(List[k], List[i]);
Perm(List, k + 1, m);
std::swap(List[k], List[i]);
}
}
}
1-n 选出 m 个数组合问题
1.递归解法
思路:递归对前n-m个数考虑选和不选
/*
select m from n
*/
function combination(m,n){
var result=[];
if(m==n){
for(var i=n;i>=1;i--){
result.push(i);
}
return [result];
}
for(var i=n;i>=m;i--) {
var sub=[i];
if(m==1) {
result.push(sub);
continue;
}
/*
select one already,then select m-1 from n-1
*/
var subs=combination(m-1,i-1);
for(var j=0;j<subs.length;j++) {
var tmp=sub.concat(subs[j]);
result.push(tmp);
}
}
return result;
}
分享到:
相关推荐
高中数学完整讲义——排列与组合7排列组合问题的常用方法总结1,推荐文档.pdf
该文档对排列组合问题的算法设计问题进行一系列讲述
数学排列与组合PPT课件.pptx
高中数学排列与组合PPT课件.pptx
高中数学选修排列与组合排列与排列数PPT课件.pptx
排列组合 排列 组合 java排列组合算法 排列组合算法
主要介绍了C#实现排列组合算法的完整实例,文中实例主要展示了排列循环方法和排列堆栈方法,需要的朋友可以参考下
1.6 允许重复的组合与不相邻的组合 1.6.1 允许重复的组合 1.6.2 不相邻的组合 1.6.3 线性方程的整数解的个数问题 1.6.4 组合的生成 1.7 组合意义的解释 1.8 应用举例 1.9 stirling公式 1.9.1 wallis公式 ....
只需改变里面一处数据,就可以根据自己需要,执行输出n个数中取m个数的所有组合。
qt c++ 排列组合 实现 没分的联系本人索要
PHP实现多种类型的排列组合算法,PHP多种方式实现排列组合算法。非常有用,欢迎下载。
excel VBA - 排列组合生成算法 - ,可快速生成指定项目的所有排列组合
组合数学之排列组合生成算法,很好的学习组合排列算法的资料
排列组合生成器,支持筛选,存储采用h2数据库,后台采用springboot框架
小小wintc程序 计算排列组合代吗 用递归写的 呵呵
高中数学选修 排列与组合 排列与排列数PPT课件.pptx
一年级数学排列与组合PPT课件.pptx
这款代码,是关于排列组合问题,多用于计算机专业考研时
Java排列组合_组合算法,利用list及set的无序性, 通过递归实现,不同于以往的排列组合 自娱自乐