全排列

[1, 2, 3] 的全排列记作 p(1, 2, 3), 可以分解为：

1. 除了 1 之外数字的全排列 p(2, 3)
2. 除了 2 之外数字的全排列 p(1, 3)
3. 除了 3 之外的数字全排列 p(1, 2)

function swap(x, t, i) {
  if (t !== i) {
    var _ = x[t]
    x[t] = x[i]
    x[i] = _
  }
}

function p(m) {
  var r = []
  // 初始化索引
  var x = []
  for (var i = 0; i < m; ++i) {
    x[i] = i
  }
  _p(0)
  return r
  function _p(t) {
    if (t >= m) {
      var _r = []
      for (var i = 0; i < m; ++i) {
        _r[i] = x[i]
      }
      r[r.length] = _r
    } else {
      for (var i = t; i < m; ++i) {
        // 逐个排除
        // 排除方法: 把排除元素放到第一个上
        swap(x, t, i)
        // 求剩余数字的全排列
        _p(t + 1)
        // 还原排除，以便于下一步循环
        swap(x, t, i)
      }
    }
  }
}

排列

从 n 个数随机抽取 m 个数，然后全排列

function pick(n, m) {
  var r = []
  var _r = p(m)
  var x = []
  var c = 0
  var count = 0
  _pick(0)
  return r
  function _pick(t) {
    if (c >= m) {
      ++count
      var q = []
      for (var i = 0; i < n; ++i) {
        if (x[i]) {
          q.push(i)
        }
      }
      for (var i = 0; i < _r.length; ++i) {
        var _i = _r[i]
        var tmp = []
        for (var j = 0; j < m; ++j) {
          tmp[j] = q[_i[j]]
        }
        r.push(tmp)
      }
      return
    }
    // 主要部分
    // 判定是否已经抽够 m 了
    // 每个数存在两种可能性: 抽中/没抽中
    if (c + 1 <= m) {
      x[t] = 1
      ++c
      _pick(t + 1)
      --c
    }
    if (n - t > m - c) {
      x[t] = 0
      _pick(t + 1)
    }
  }
}

八皇后问题

使用 React 把结果渲染出来 DEMO

function queen(n) {
  var q = []
  var r = []
  _queen(0)
  return r

  function check (t) {
    for (var i = 0; i < t; ++i) {
      if (
        // 列不冲突
        q[i] === q[t] ||
        // 对角不冲突
        (t - i) === Math.abs(q[t] - q[i])
      ) {
        return false
      }
    }
    return true
  }

  // 逐行处理
  function _queen(line) {
    if (line >= n) {
      var _r = []
      for (var i = 0; i < n; ++i) {
        _r.push(q[i])
      }
      r.push(_r)
    } else {
      // 可能性列遍历
      for (var col = 0; col < n; ++col) {
        // 每列存在两种可能: 放或不放
        q[line] = col
        // 放，则检查是否满足
        // 满足时，开始下一行
        // 不满足时，尝试下一种可能性
        if (check(line)) {
          _queen(line + 1)
        }
      }
    }
  }
}

台阶

有10步楼梯,每次走1步或两步 问有多少走法。当然可以使用 https://www.zybang.com/question/fd00eb608849e0a845a3a8d49e55c6d1.html 这里的方法

// n: {number} 表示楼梯共多少步
// p: {array} 支持的步数 ex: [1, 2]
function steps (n, p) {
  // 存储各种走法
  var tmp = []
  // 多少种走法
  var count = 0
  // 已走过楼梯数
  var c = 0
  _steps()
  return count
  function _steps() {
    // 可能性步数遍历
    for (var i = 0; i < p.length; ++i) {
      var step = p[i]
      // 可以走或不走当前 step
      // 1. 走当前 step
      tmp.push(step);
      c += step;
      // 走的话，就判定下是否满意条件
      if (c < n) {
        _steps()
      } else if (c === n) {
        count++
        // console.log(tmp)
      }
      // 2. 不走当前 step
      tmp.pop()
      c -= step
    }
  }
}