文档章节

用 JavaScript 实现全排列算法

刘军兴
 刘军兴
发布于 2016/10/20 14:22
字数 463
阅读 128
收藏 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
博文 184
码字总数 226359
作品 0
昌平
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
05/10
0
0
[javascript]实现汉字Unicode编码的转换

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

jn_王文強
2013/06/29
0
2
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
javascript 垃圾回收算法了解一下

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

程序员解决师
06/12
0
0
javascript中的线程之我见

今天与一个同事争论javascripe中间的线程机制,他争论说javascript是有线程的,理由即使javascript中间的事件回调就是线程的实现,个人认为在javascript中是没有线程机制的 理由如下: 引自《...

mj4738
2013/02/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

flume -- fileChannel简要分析其过程

flume之event写入FileChannel doPut(event)-->获取共享锁后[log.lockShared();]-->FlumeEventPointer ptr = log.put(transactionID, event); 此处的log.put即将transactionID及event进行后续......

-九天-
36分钟前
2
0
Linux与FreeBSD有什么区别?

基础 许多人所称的“Linux”实际上不是 Linux。Linux 从技术上说只是 Linux 内核,典型的 Linux 发行版则包括了 Linux 内核和许多软件。这是为什么 Linux 有时被称为 GNU/Linux。事实上,许多...

linux-tao
44分钟前
3
0
jQuery学习笔记180924

jQuery - AJAX 简介 什么是 AJAX? AJAX = 异步 JavaScript 和 XML(Asynchronous JavaScript and XML)。 简短地说,在不重载整个网页的情况下,AJAX 通过后台加载数据,并在网页上进行显示...

颖伙虫
57分钟前
1
0
springboot整合vue小试牛刀

序 本文主要研究一下如何在springboot工程整合vue maven <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-we......

go4it
58分钟前
2
0
使用python的profiler工具

主要用来检测python coding的执行时间 fly profiler

steel7c4
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部