欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用递归与循环实现排列算法

程序员文章站 2022-04-07 12:34:12
...

排列就是从n个数中取出m个数(考虑数的顺序)来有几种情况。这个是数学上的定义,可能比较难理解。比较生活化的角度来看就是从一盒装有一个红球、一个黄球、一个绿球、一个白球和一个黑球的箱子中去出3个球来(考虑球的顺序)有几种情况。排列算法就是为了解决这类问题而发明出来的。

我们可以用画树形图的方法来解决这个问题:

用递归与循环实现排列算法


从上图可以看出从['A', 'B', 'C', 'D']中取3个数来排列有6 * 4 = 24中情况。那么问题来了,我们应该如何用程序实现树形图的求解过程呢?其实我们可以看出,要取出几个数就要画几层,每一层其实是对数据的一次遍历,而且每一层的操作都是类似的,因此我们可以用递归和循环来实现这个树形图的求解过程。代码如下(JS语言描述):

<!doctype html>
<html>
<head>
  <meta charset="UTF-8">
  <meta name="viewport"
        content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>排列组合</title>
  <script>
    var arr = ['A', 'B', 'C', 'D'];
    var count = 3;
    var iNow = 1;

    function rangeCombination(arr, count) {
      var resultNum = 0;

      if (count == 1) {
        return arr.length;
      }
      function change(arr, iNow) {

        for (var i = 0; i < arr.length; i++) {
          var result = arr.concat();
          result.splice(i, 1);
          if (count == iNow) {
            resultNum += result.length;
          } else {
            change(result, iNow + 1);
          }

        }

      }
      change(arr, iNow + 1);


      return resultNum;
    }
    console.log(rangeCombination(arr, count));
  </script>
</head>
<body>

</body>
</html>



相关标签: 数据结构 js