全排列思想

全排列的思想

从 n 个不同元素中任取 m（m<=n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m=n 时所有的排列情况叫全排列。
这时候我们就可以来思考，如何取得所有排列的情况。
例如数组[1, 2, 3, 4]，我们可以先固定一个数字1，这时候剩下的数组就变成了[2, 3, 4]。
此时再固定一个数字2，数组剩下[3, 4]。
再固定3，这时候数组就只剩下[4]，就可以输出一个序列 -> [1, 2, 3, 4]。
这时候将3解除固定，与4交换，再固定4，这时又可以输出一个序列 -> [1, 2, 4, 3]。
这样固定1, 2时候的所有情况就排列出来了，再继续将2解除固定，并与3交换。
这时候就固定了1, 3，数组剩下[2, 4]，再重复上面的方法，直到所有固定两个数的排列都排完后，再交换固定的第一个数，这样就可以推出全排列。

递归的实现

function Perm(arr, current, count) {
  // 前面的数都已固定完
  if (current == count) {
    let str = ""
    for (let i = 0; i <= count; i++) {
      str += arr[i]
    }
    console.log(str)
  } else {
    for (let i = current; i <= count; i++) {
      // 不相同才交换
      if (sample(arr, current, i)) {
        // 将数字挨个交换
        ;[arr[i], arr[current]] = [arr[current], arr[i]]

        // 交换后执行递归函数
        Perm(arr, current + 1, count)

        // 数字交换后需要复原
        ;[arr[i], arr[current]] = [arr[current], arr[i]]
      }
    }
  }
}
function sample(arr, start, end) {
  for (let i = start; i < end; i++) {
    if (arr[i] == arr[end]) {
      return false
    }
  }
  return true
}
let arr = [1, 2, 2, 1]
Perm(arr, 0, arr.length - 1)

结果：

1221
1212
1122
2121
2112
2211

非递归的实现

** 会重复 **

function permutation(arr) {
  let total = 1
  // 计算排列种数
  for (let i = 2; i <= arr.length; i++) {
    total *= i
  }
  print_r(arr)
  for (let i = 0; i < total; i++) {
    let k = arr.length - 1,
      min = Number.MAX_VALUE,
      minIndex = 0
    // 从后开始遍历，找到底一个非增的元素，和后面某个刚好大于它的元素替换
    while (k > 0 && arr[k] < arr[--k]);

    // 找到刚好比替换到前面大的元素
    for (let j = arr.length - 1; j >= k + 1; j--) {
      if (arr[j] > arr[k] && min > arr[j]) {
        min = arr[j]
        minIndex = j
      }
    }

    //与找到的元素 进行交换
    ;[arr[k], arr[minIndex]] = [arr[minIndex], arr[k]]

    // 数组倒置
    for (let m = 0; m < (arr.length - k - 1) / 2; m++) {
      ;[arr[k + 1 + m], arr[arr.length - 1 - m]] = [
        arr[arr.length - 1 - m],
        arr[k + 1 + m],
      ]
    }
    print_r(arr)
  }
}

function sample(arr, start, end) {
  for (let i = start; i < end; i++) {
    if (arr[i] == arr[end]) {
      return false
    }
  }
  return true
}

function print_r(arr) {
  let str = ""
  for (let i = 0, len = arr.length; i < len; i++) {
    str += arr[i]
  }
  console.log(str)
}