排列与组合

排列和组合（permutations and combinations），是指从一个集合中选择对象的各种方式，一般不替换（replacement），以形成子集。当选择的顺序是一个元素时，这种子集的选择被称为排列，当顺序不是一个元素时，被称为组合。

实现

JavaScript

/*
 * Problem Statement: Generate all distinct permutations of a an array (all permutations should be in sorted order);
 *
 * What is permutations?
 * - Permutation means possible arrangements in a set (here it is an array);
 *
 * Reference to know more about permutations:
 * - https://www.britannica.com/science/permutation
 *
 */

const swap = (arr, i, j) => {
  const newArray = [...arr];

  [newArray[i], newArray[j]] = [newArray[j], newArray[i]] // Swapping elements ES6 way

  return newArray
}

const permutations = arr => {
  const P = []
  const permute = (arr, low, high) => {
    if (low === high) {
      P.push([...arr])
      return P
    }
    for (let i = low; i <= high; i++) {
      arr = swap(arr, low, i)
      permute(arr, low + 1, high)
    }
    return P
  }
  return permute(arr, 0, arr.length - 1)
}

参考

• permutations and combinations | Description, Examples, & Formula | Britannica (opens new window)