文档章节

用 JavaScript 实现全排列算法

刘军兴
 刘军兴
发布于 2016/10/20 14:22
字数 463
阅读 169
收藏 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, 然后在回调中实现自己的业务.

 

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 56
博文 189
码字总数 231687
作品 0
昌平
私信 提问
刷《一年半经验,百度、有赞、阿里面试总结》·手记

在掘金上看到了一位大佬发了一篇很详细的面试记录文章-《一年半经验,百度、有赞、阿里面试总结》,为了查漏补缺,抽空就详细做了下。(估计只有我这么无聊了哈哈哈) 有给出的或者有些不完善...

大灰狼的小绵羊哥哥
12/03
0
0
[javascript]实现汉字Unicode编码的转换

js文件中,有些变量的值可能会含有汉字,画面引入js以后,有可能会因为字符集的原因,把里面的汉字都变成乱码。后来发现网上的一些js里会把变量中的汉字都表示成”u“开头的16进制编码,这样...

jn_王文強
2013/06/29
0
2
全栈 JavaScript 程序员的崛起

原文地址:http://thefullstack.xyz/full-stack-javascript-developer/ JavaScript 无处不在 在以前,JavaScript程序员就是前端开发者的同义词,永远与浏览器绑在一起。 但那已是昨日往事。N...

oschina
2016/06/08
7.7K
43
Event Loop 这个循环你晓得么?(附GIF详解)

Event Loop 这个循环你晓得么?(附GIF详解) setTimeout(() => {console.log(2);setTimeout(() => { }, 0) ;}, 0); setTimeout(() => {console.log(5);setTimeout(() => { }, 0);}, 0); cons......

罂粟
08/29
0
0
腾讯移动前端框架 mt 2.0 发布

MT是手机腾讯网前端团队开发维护的一个专注于移动端的js模块管理框架。 Git:http://git.oschina.net/luyongfugx/mt mt介绍文档:http://mt.tencent.com/mt1index.html 为什么使用MT 无更新不...

oschina
2014/06/11
8.7K
21

没有更多内容

加载失败,请刷新页面

加载更多

【转载】缓存穿透,缓存击穿,缓存雪崩解决方案分析

前言 设计一个缓存系统,不得不要考虑的问题就是:缓存穿透、缓存击穿与失效时的雪崩效应。 缓存穿透 缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时被动写的,并且出于容错考虑...

xiaomin0322
8分钟前
0
0
Maven: Non-resolvable import POM:Failure to find *** in *** was cached in the local repository.

clean or package spring cloud 项目时,IDE 打印如下报错: Non-resolvable import POM: Failure to find org.springframework.cloud:spring-cloud-dependencies:pom:Greenwich.M3 in https......

AmosWang
12分钟前
0
0
性能优化(性能优化概述)

软件系统质量特性 安全性 同时兼顾向合法用户提供服务,以及阻止非授权使用软件及资源的能力。 健壮、可靠 软件系统在一定的时间内无故障运行的能力、容错能力、恢复能力 。 可用性、易用性、...

这很耳东先生
16分钟前
0
0
ZooKeeper命令大全

创建节点 # 创建节点,-s表示顺序节点,-e表示临时节点,默认是持久节点create [-s] [-e] path data acl # 示例create /zk-book 123 查看节点 ls path [watch] # 示例ls /zk-book 获取...

爱宝贝丶
26分钟前
2
0
Elasticsearch节点角色类型node.master和node.data说明s

一般地,ElasticSearch集群中每个节点都有成为主节点的资格,也都存储数据,还可以提供查询服务。这些功能是由两个属性控制的(node.master和node.data)。默认情况下这两个属性的值都是tru...

傲娇字符
42分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部