hanyeah

递增进位制法 

这个算法是基于序列的递增进位制数。递增进位制数是指数字的进制随着位数的递增而递增。一般情况下，数字最右边的进制是2，次右边的进制是3，以此类推。n位递增进位制数一共包含n!个数字，所以它可以与全排列生成算法结合在一起。

算法步骤 

由于在字典序法中由中介数求排列比较繁琐，可以通过另外定义递增进位制数加以改进。定义: i的右边比i小的数字的个数, 则()↑为递增进位制法中定义的中介数，这里的中介数是递增进位制数字。例如，839647521对应的中介数为(67342221) ↑。由中介数求排列时，从大到小根据求出n,n-1,…,2,1的位置——从右向左将第+1个空填上i，剩下的最后一个空位填上1。因此根据“原排列”→“原中介数”→“新中介数”→”新排列“，在这样的定义下，可以求出下一个排列。所以根据递增进位制法生成全排列步骤如下：

1. 初始化中介数（每一位都为0） 

2. 根据中介数求出对应的排列，输出排列

3. 如果没有输出所有的排列——中介数+1（这里是递增进位制数字的加法，区别于一般的十进制加法），跳回步骤（2）

如果已经输出所有的排列——结束 

算法正确性证明 

对于一个给定的中介数，对应于一个唯一的排列，这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递增递减进位制数字有(m+1)！个，因此对于一个m位的中介数可能的取值有(m+1)！。又因为中介数与排列一一对应，所以由m位的中介数可以求出(m+1)！个排列。一个m位的中介数对应m+1个数字，m+1个不同元素的全排列有(m+1)！个。因此递增进位制法可以生成全排列。

https://zh.wikipedia.org/wiki/%E5%85%A8%E6%8E%92%E5%88%97%E7%94%9F%E6%88%90%E7%AE%97%E6%B3%95

通过这种中介数求原排列非常的简便，中介数k[i]表示真实数n-i处于从右往左数第i个（之前已经存在的数不算），我们称此为空格法。

例如求342221的原排列 

①__ __ ____ __ __ __第7位数字是3，我们从右向左数3个空格，再往前数一个空格，空格中填入对应的位数7。  

②__ __ __7 __ __ __。第6位数字是4，我们从右向左数4个空格，其中已经放上数的不算空格，再往前数一个空格，空格中填入6。 

③__ 6 __7 __ __ __。接下来的步骤也是一样的，第5位的数字是2，数2个空格，再往前数一个空格填入5。  

④__ 6 __7 5 __ __。第4位是2，数2个空格再往前数一个空格填入4。 

⑤__ 6 4 7 5 __ __。第3位是2，数2个空格再往前数一个空格填入3。 

⑥3 6 4 7 5 __ __。第2位是1，数1个空格，再往前数一个空格填入2。 

⑦3 6 4 7 5 2 __。第1位是0，数0个空格，再往前数一个空格填入1。 

由此，我们得到了原来的排列3 6 4 7 5 2 1。

https://www.imooc.com/article/41732?block_id=tuijian_wz

实现代码：

var n = 4;
var agency = [];
var num = [];
var result = [];
for(var i = 0; i < n; i++) {
	agency[i] = 0;
}

function agency2num() {
	num.length = 0;
	for(var i = 0; i < n; i++) {
		var c = agency[i];
		for(var j = n - 1; j >= 0; j--) {
			if(isNaN(num[j])) {
				c--;
				if(c < 0) {
					num[j] = n - i;
					break;
				}
			}
		}
	}
}

do{
	agency2num();
	result.push([agency.concat().join(),num.concat().join()]);
} while(!agencyPlusPlus());

console.table(result);

function agencyPlusPlus() {
	var i = 1;
	var add = 1;
	while(add && n - i >= 0){
		agency[n - i] += add;
		add = 0;
		if(agency[n - i] >= i) {
			agency[n - i] = 0;
			add = 1;
		}
		i++;
	}
	return add;
}