前端知识体系

Appearance

大纲

写一个全排列、全组合的函数 ​

排列组合是组合学最基本的概念。

  • 所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。
  • 组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

排列英文名叫 Arrangement 或者 Permutation，本文采用 Arrangement 来表示排列，下文统称为 A（跟新教材统一，避免和 P 概率混淆）。

组合英文名叫 Combination，下文统称为 C。

A 和 C 的本质区别在于：决策的顺序对结果有没有影响。

公式 ​

此处使用 markdown-it-mathjax3, 一个从 markdown-it-katex 改造而来、额外增加了 MathJax v3 和 SVG 渲染支持的插件。

VSCode 中推荐使用 LaTeX Workshop 插件

LaTeX 示例：

x=−b±b2−4ac2a

对于排列组合，可以使用 \binom{n}{m} 或 {n \choose m} 来表示公式，更多参考 莱斯大学 LaTex Math 在线 PDF 手册

排列公式 ​

A(n,m)=Anm=n!(n−m)!

组合公式 ​

C(n,m)=Cnm=n!(n−m)!⋅m!

C(n, m) 也记作 (nm)

算法实现 ​

排列算法 ​

全排列：给定一个数组，返回所有排列。

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var arrangement = function (nums) {
  let result = []
  let used = Array.from({ length: nums.length }).fill(false)
  function search(collection, used) {
    if (collection.length === nums.length) {
      result.push(collection)
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i] === false) {
        used[i] = true
        search(collection.concat(nums[i]), used.slice(0))
        used[i] = false // 重置状态
      }
    }
    collection = null
    used = null
  }
  search([], used)
  return result
}

// testing
console.log(arrangement([1, 2, 3]))

思路解析：

遍历每个数，满足条件，递归调用，满足条件就 push，直到 for 结束

组合算法 ​

全组合：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

js
var combine = function (n, k) {
  let result = []
  function find(collection, from) {
    if (collection.length === k) {
      result.push(collection)
      return
    }
    for (let i = from; i <= n; i++) {
      find(collection.concat(i), i + 1)
    }
  }
  find([], 1)
  return result
}

// testing
console.log(combine(5, 3))

思路解析：

遍历每个数，递归调用，满足条件就 push，直到 for 结束

输出所有的可能的子数组 ​

写一个方法，输出所有的可能的子数组

js
function power(s) {
  return s.reduce((p, e) => p.concat(p.map((sub) => sub.concat([e]))), [[]])
}

// testing
console.log(power([1, 2, 3]))

// 执行分析
// [[]]
// [[],[1]]
// [[],[1],[2],[1,2]]
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

参考