今天讲一讲高中数学学过的排列组合算法

排列

所谓排列,就是将一个集合中的所有成员,按照一定的顺序排列起来

例如, 对于集合S={A,B,C} 可能的排列有6种:

{A,B,C}

{A,C,C}

{B,A,C}

{B,C,C}

{C,A,B}

{C,B,A}

对于一个N个元素构成的集合,其全排列有N!中,其中的道理很简单:

  1. 从N个元素中选择一个元素有N中可能
  2. 第一个元素确定后,第二个元素的可能的选择有N-1中

以此类推,可知可能的排列为:N * (N -1 ) * (N -2 ) * ... * 1 = N!

如何编程实现?

字典顺算法

算法步骤:

  1. 将输入的数组arr按照升序排序
  2. 从后往前找到arr中的第一个递减元素arr[i] > arr[i - 1],如果找不到则程序结束
  3. 找出arr开始的最小元素arr[j]
  4. 交换arr[j]arr[i - 1]
  5. arr下标i到数组最后一个元素升序排序
  6. 重复上述步骤

该算法能保证产出的结果是按照升序排列的


export const permutation = (arr: Array<number>) => {
  if (arr.length < 2) {
    return arr
  }
  const copy = [...arr].sort() // step 1
  const res = []
  while (true) {
    res.push([...copy])
    let position = -1
    for (let i = copy.length - 1; i > 0; i--) { // step 2
      if (copy[i] > copy[i - 1]) {
        position = i - 1
        break
      }
    }
    if (position === -1) {
      break
    }
    let rightMin = -1
    for (let i = copy.length - 1; i > position; i--) { // step3
      if (copy[i] > copy[position]) {
        rightMin = i
        break
      }
    }
    swap(copy, rightMin, position) //step 4
    sort(copy, position + 1, copy.length - 1) // step 5
  }
  return res

}
export function swap(arr: Array<number>,a: number,b: number) {
  const tmp = arr[a]
  arr[a] = arr[b]
  arr[b] = tmp
}
export function sort(arr: Array<number>, from: number, to: number) {
  if (arr.length < 2) {
    return
  }
  for (let i = from; i <= to; i++) {
    let min = i
    for (let j = i + 1; j <= to; j++) {
      if (arr[j] < arr[i]) {
        min = j
      }
    }
    if (arr[min] < arr[i]) {
      swap(arr, i, min)
    }
  }
}


组合

组合不考虑元素的顺序

递归算法


import { swap, sort } from './permutation'
// 递归实现
export const combineR = (arr: Array<any>, length: number): Array<any> => {
  if (length === 1) {
    return arr.map(v => [v])
  }
  if (arr.length === length) {
    return [arr]
  }
  const [first, ...rest] = arr
  const base: Array<any> = combineR(rest, length - 1).map((item: Array<any>) => [first, ...item])
  if (rest.length >= length) {
    return [...base, ...combineR(rest, length)]
  }
  return base
}

非递归算法


// 非递归实现
// 思想和排列类似, 用一个数组表示元素的选取,1表示取,0表示者不取,然后依次增加

export const combine = (arr: any, count: number) => {
  const flags = [...Array(arr.length - count).fill(0), ...Array(count).fill(1)]
  const res = []
  while (true) {
    res.push([...flags])
    let position = -1
    for (let i = flags.length - 1; i > 0; i--) {
      if (flags[i] > flags[i - 1]) {
        position = i - 1
        break
      }
    }
    if (position === -1) {
      break
    }
    swap(flags, position, position + 1)
    sort(flags, position + 1, flags.length - 1)
  }
  return res.map(c => {
    const r:Array<any> = []
    c.forEach((v, i) => {
      if(v === 1) { r.push(arr[i])}
    })
    return r
  })

}