文档章节

用 JavaScript 实现全排列算法

刘军兴
 刘军兴
发布于 2016/10/20 14:22
字数 463
阅读 96
收藏 0
点赞 0
评论 0

全排列的算法参见网页:

使用递归的方法实现的全排列算法: 
    http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html

使用字典序方法实现的: 
  http://blog.csdn.net/joylnwang/article/details/7064115

 

下面用 js 实现它们, 因为我们在程序中要使用:

// 使用递归的方法实现的全排列算法: http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
function perm(arr, k, array_size) {
  if (k >= array_size) {
    console.log('perm: ', arr);  // 输出找到的一个全排列.
  }
  else {
    for (var i = k; i < array_size; ++i) {
      swap(arr, k, i);
      perm(arr, k+1, array_size);  // 递归.
      swap(arr, k, i);  // 再交换回来.
    }
  }
  
  function swap(arr, i, j) {
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  } 
}

// 使用例子:
perm([1,2,3,4], 0, 4);

 

字典序的:

// 按照字典序算法 求数组 array 的下一个排列.
// http://blog.csdn.net/joylnwang/article/details/7064115
function perm_next(array) {
  var n = array.length;
  
  // 找到所有满足 a[k]<a[k+1](0<k<n-1) 的 k 的最大值.
  var k = n - 2;
  while (k != -1 && array[k] > array[k+1])
    --k;
  // 达到字典序最大值了, 则所有排列输出完毕.
  if (k == -1) 
    return false;

  // 在区间 [k+1, n] 找元素 l, 使得在所有 a[l]>a[k] 的元素中, a[l] 取得最小值.
  var l = -1;
  for (var j = n - 1; j > k; --j) {
    if (array[j] > array[k]) {
      if (l == -1 || array[j] < array[l])
        l = j;
    }
  }
  
  // 交换 a[k],a[l].
  swap(array, k, l);
  
  // 反转区间 a[k+1 ... n] 内的元素顺序.
  reverse(array, k+1, n-1);
  
  return true;
  
  // 交换数组中两个元素.
  function swap(array, i, j) {
    var tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }
  
  // 反转数组 array 区间 [first ... last] 的元素.
  function reverse(array, first, last) {
    for (var i = first; i < last; ++i, --last) {
      var tmp = array[i];
      array[i] = array[last];
      array[last] = tmp;
    }
  }
}

// 使用例子:
var array = [1, 2, 3, 4, 5];
do {
  console.log(array);  // 输出一个排列
} while (perm_next(array));

 

可以将调用 console.log() 的地方改为调用 callback, 然后在回调中实现自己的业务.

 

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 54
博文 150
码字总数 226172
作品 0
昌平
javascript 垃圾回收算法了解一下

我们通常理解的 javascript 垃圾回收机制都停留在表面,"会释放不被引用变量内存",最近在读《深入浅出node.js》的书,详细了解了下 v8 垃圾回收的算法,记录了一些学习笔记。 敲黑板:v8引擎...

程序员解决师 ⋅ 06/12 ⋅ 0

以变制变——前端动态化代码保护方案探索

欢迎大家前往腾讯云+社区,获取更多腾讯海量技术实践干货哦~ 本文分享了腾讯防水墙团队关于机器对抗的动态化思路,希望能抛砖引玉,给现在正在做人机对抗的团队一些启发,帮助更多中小型公司...

腾讯云加社区 ⋅ 06/07 ⋅ 0

深入框架本源系列 —— Virtual Dom

该系列会逐步更新,完整的讲解目前主流框架中底层相通的技术,接下来的代码内容都会更新在 这里 为什么需要 Virtual Dom 众所周知,操作 DOM 是很耗费性能的一件事情,既然如此,我们可以考虑...

夕阳 ⋅ 06/02 ⋅ 0

实现多个标签页之间通信的几种方法(sharedworker)

示例地址 prologue 之前在网上看到一个面试题:如何实现浏览器中多个标签页之间的通信。我目前想到的方法有三种:使用websocket协议、通过localstorage、以及使用html5浏览器的新特性SharedW...

ITgecko ⋅ 04/11 ⋅ 0

JavaWeb01-HTML篇笔记(七)

.1 案例三:完成对注册页面的数据的简单校验.1.1.1 需求: 对注册页面的数据进行非空的简单校验!!!如果有某个值没有输入,点击提交,弹出一个对话框进行提示!! 1.1.2 分析:1.1.2.1 技术分...

我是小谷粒 ⋅ 04/28 ⋅ 0

用 TensorFlow.js 在浏览器中训练神经网络

本文结构: 什么是 TensorFlow.js 为什么要在浏览器中运行机器学习算法 应用举例:regression 和 tflearn 的代码比较 1. 什么是 TensorFlow.js TensorFlow.js 是一个开源库,不仅可以在浏览器...

不会停的蜗牛 ⋅ 前天 ⋅ 0

四月前端知识集锦(每月不可错过的文章集锦)

目前自己组建的一个团队正在写一份面试图谱,将会在七月中旬开源。内容十分丰富,第一版会开源前端方面知识和程序员必备知识,后期会逐步写入后端方面知识。因为工程所涉及内容太多(目前已经...

夕阳 ⋅ 05/02 ⋅ 0

【Vue】源码分析--vdom与html的相互转换

简析 vdom是由js对象节点组成的一个树状结构,通过diff算法对比js对象节点来更新,最后映射到原生的dom中 一个简单的dom结构 对应到js对象节点就是 代码实现 index.html vNode.js Github htt...

ns2250225 ⋅ 03/13 ⋅ 0

JavaScript中的this指针 理论化this指针的定义

JavaScript现在应用之广泛,远超其他任何语言,只要是一个合格的网站应用,基本上多多少少都会有JS的存在。在JavaScript中,this的指向被不少Coder所不解,但其实JS中的this理解起来也是相当...

superwebmaster ⋅ 05/29 ⋅ 0

五月前端知识集锦(每月不可错过的文章集锦)

目前自己组建的一个团队正在写一份面试图谱,将会在七月中旬开源。内容十分丰富,第一版会开源前端方面知识和程序员必备知识,后期会逐步写入后端方面知识。因为工程所涉及内容太多(目前已经...

夕阳 ⋅ 05/28 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

【elasticsearch】 随笔 Date datatype

一。时间类型的本质 首先json是没有时间类型的,对于es来说,时间类型的标示可以是下面三种情况 1.一个时间格式的字符串,如:"2014-11-27T08:05:32Z","2015-01-01" or "2015/01/01 12:10:3...

xiaomin0322 ⋅ 14分钟前 ⋅ 0

阿里云资源编排ROS使用教程

阿里云资源编排ROS详细内容: 阿里云资源编排ROS使用教程 资源编排(Resource Orchestration)是一种简单易用的云计算资源管理和自动化运维服务。用户通过模板描述多个云计算资源的依赖关系、...

mcy0425 ⋅ 16分钟前 ⋅ 0

适配器设计模式

1、适配器模式 把一个类的接口变换成客户端所期待的另一种接口 使原本因接口不匹配而无法在一起工作的两个类能够在一起工作 分为类的适配器模式和对象的适配器模式 2、类适配器模式 类的适配...

职业搬砖20年 ⋅ 20分钟前 ⋅ 0

npm操作报错 _stream_writable.js:61

有一天 不知道什么原因(估计和node的版本有关),无论你做什么npm的操作 都会报错/usr/local/lib/node_modules/npm/node_modules/readable-stream/lib/_stream_writable.js:61 这时候只要执...

lilugirl ⋅ 24分钟前 ⋅ 0

Eclipse安装插件的几种方式

Eclipse魅力之一就是支持可扩展的插件,来丰富自身的功能,这种方式也是建立在开源思想之上的。具体使用什么方式去安装插件,要看我们拿到的是什么。 1. 拿到的是一串URL,如http://subclips...

GordonNemo ⋅ 26分钟前 ⋅ 0

div图片叠加

css实现代码如下: <div style="position: relative;"><!--这个层为外面的父层,需设置相对位置样式--> <div style="position: absolute;"><!--子层,需设置绝对位置样式--> <i......

niithub ⋅ 28分钟前 ⋅ 0

作用域slot

如果父组件需要使用子组件中的内容怎么办,比如父组件需要控制子组件的显示 <div id="root"><child><template slot-scope="props"><h1>{{props.item}} <div>编辑</div></h1><......

金于虎 ⋅ 30分钟前 ⋅ 1

HongHu commonservice-eureka 项目构建过程

上一篇我们回顾了关于 spring cloud eureka的相关基础知识,现在我们针对于HongHu cloud的eureka项目做以下构建,整个构建的过程很简单,我会将每一步都构建过程记录下来,希望可以帮助到大家...

明理萝 ⋅ 33分钟前 ⋅ 1

xml和对象的相互转化

@Data//setter和getter方法,toString和equals,hashcode方法@EqualsAndHashCode//代表重写equals和hashcode方法@XmlAccessorType(XmlAccessType.FIELD)public class Classroom {@X......

拐美人 ⋅ 33分钟前 ⋅ 0

tableView cell的高度 分组头部尾部的高度 自适应

@property (nonatomic) CGFloat rowHeight; // default is UITableViewAutomaticDimension@property (nonatomic) CGFloat sectionHeaderHeight; // default is UITableViewA......

娜一片蓝色星海 ⋅ 35分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部