排列穷举算法

February 19, 2019

递归版的排列穷举算法如下:

首先选择第 11 个元素,这等价于原列表 1...n1...n 中选择一个元素与第 11 个元素交换位置。再选择第 22 个元素,等价于从所有元素除去第一个选择中选择一个与其交换,而这些元素刚好位于列表现在的 2...n2...n 位置中。依次递归。

function* permutationR(A) {
  const len = A.length;

  function* permu(s) {
    if (s === len) {
      yield A;
      return;
    }
    for (let i = s; i < len; i++) {
      [A[s], A[i]] = [A[i], A[s]];
      yield* permu(s + 1);
      [A[s], A[i]] = [A[i], A[s]];
    }
  }
  yield* permu(0);
}

考虑迭代版:

从上往下不断深入第一个子节点,沿途访问,并将下端节点入栈。到终点后弹出栈,访问这个最后入栈的下端节点。这个下端节点由兄弟吗?如果有,下次节点展开此兄弟展开。如果没有,继续弹出栈中它的父下端节点,访问,这个父下端节点如果有兄弟,下次节点将从它展开,如果没有,继续弹出直到获取下次深入的起点。

我们用如下 Node 模拟上面的递归实例。

class Node {
  constructor(base, target) {
    this.base = base;
    this.target = target;
  }
  isValid(max) {
    return (this.base < max && this.target < max);
  }
  swap(A) {
    [A[this.base], A[this.target]] = [A[this.target], A[this.base]];
  }
  getFirstChild() {
    return new Node(this.i+base, this.i+target);
  }
  getCousin() {
    return new Node(this.base, this.target+1);
  }
}

上面的“访问”对应于 swap 操作,获取兄弟对应于下次 for 循环。

function* permutationI(A) {
  const len = A.length;

  const stack = [];
  let curr = new Node(0,0);
  while (true) {

    while (curr.isValid(len)) {
      curr.swap(A); // “访问”上端子节点
      stack.push(curr); // 下端子节点刚好和上端一样
      curr = curr.getFirstChild();
    }

    yield A; // 到达最深处

    while (true) { // 寻找兄弟节点
      if (stack.length === 0) {
        return;
      }
      const node = stack.pop();
      node.swap(A);
      const cousin = node.getCousin();
      // 如果没有兄弟转向父节点回溯
      if (cousin.isValid(len)) {
        curr = cousin;
        break;
      }
    }
  }
}

输出

for (var permu of permutationR(['a','b','c'])) {
  console.log(permu);
}
// [ 'a', 'b', 'c' ]
// [ 'a', 'c', 'b' ]
// [ 'b', 'a', 'c' ]
// [ 'b', 'c', 'a' ]
// [ 'c', 'b', 'a' ]
// [ 'c', 'a', 'b' ]