hanyeah

邻位对换法

该算法由Johnson-Trotter首先提出，是一个能快速生成全排列的算法。它的下一个全排列总是上一个全排列对换某相邻两位得到的。如果已知n-1个元素的排列，将n插入到排列的不同位置，就得到了n个元素的排列。用这种方法可以产生出任意n个元素的排列。这个方法有一个缺点：为了产生n个元素的排列，我们必须知道并存储所有n-1个元素的排列，然后才能产生出所有n阶排列。  

算法步骤

1. 初始化n个元素的排列为123……n，并规定其元素的方向都是向左的，元素的方向用一个数组b来表示，当b[i]=0，表示第i个元素的方向向左，当b[i]=1时表示地i个元素的方向向右。

2. 在排列中找出排列中所有处于活动状态的元素中最大的一个。

3. 将它与它所指向相邻元素交换。

4. 把排列中大于上面找出的处在活动状态的最大元素大的其他元素的方向倒转。

算法正确性证明

假设其对n个元素能生成全排列，只需要证明其对n+1个元素，也能生成全排列，对于新进来的元素，将其认为值最大，插入最右方，每次从右移到左，或者改变方向后从左移到右就可以认为对于一个排列从不同位置插入生成一个新的排列，而对于n个元素是全排列的，因此对于n+1个元素也是全排列的，因此邻位对换法能生成全排列。

代码如下：

var LEFT = -1;
var RIGHT = 1; 
var a = [];
var dir = [];
var n = 5;
var result = [];
// 初始化n个元素的排列为123……n，并规定其元素的方向都是向左的，元素的方向用一个数组b来表示，当b[i]=0，表示第i个元素的方向向左，当b[i]=1时表示地i个元素的方向向右。
for(var i = 0; i < n; i++){
	a[i] = i + 1;
	dir[i] = LEFT;
}

do{
	result.push(a.join());
} while(next());

console.log(result);

function next() {
	// 在排列中找出排列中所有处于活动状态的元素中最大的一个。
	var j = -1;
	var max = -1;
	for(var i = 0; i < n; i++) {
		if(a[i + dir[i]] < a[i]) {
			if (a[i] > max) {
				max = a[i];
				j = i;
			}
		}
	}
	if(j === -1) {
		return false;
	}
	// 将它与它所指向相邻元素交换。
	var ti = j + dir[j];
	var temp = a[j];
	a[j] = a[ti];
	a[ti] = temp;
	var tempDir = dir[j];
	dir[j] = dir[ti];
	dir[ti] = tempDir;
	// 把排列中大于上面找出的处在活动状态的最大元素大的其他元素的方向倒转。
	for(var i = 0; i < n; i++) {
		if(a[i] > temp) {
			dir[i] = -dir[i];
		}
	}
	return true;
}