排列生成

继续读TAOCP笔记，上次就准备写，一直没写。上次到格雷码再往后就没看了，看了非2进制格雷码。然后就来看排列生成。平时没时间看，只有厕所的时候翻一下。

排列生成给的第一个基本算法是一个老算法，但是看上去却不是那么明显的一个算法。初始化的a[1] <= a[2] <=... <= a[n]，然后生成所有按字典序的排列。

  while(1)
  {
1   VISIT(a);

2   j = n - 1; 
    while(a[j] >= a[j+1] && j > 0)
      j--;
    if(j == 0)return;

3   l = n;
    if(a[j] >= a[l])
      l --;
    swap(a[l], a[j]);

4   k = j + 1; l = n;
    while(k < l)
    {
      swap(a[k], a[l]);
      k ++; 
      l --;
    }
  }

这算法看上去一点都不明显，除掉外面的大循环，里面就是每次按照当前的a得到下一个字典序的a。 书上解释了这个算法的几个大步和历史。不过这个笔记记录我当时另外的一个方式来理解。从一个比较蠢的算法开始，得到本质上一致的解释。 一个明显简单的算法是：

per(a, i)
{
  if(i > N)
  {
    VISIT(a);
    return;
  }
  a[i] = 0;
  while(1)
  {
    a[i] = alloc(a[i]);
    if(a[i] == -1)
    {
      return;
    }  
    per(a, i + 1);
    free(a[i]);     
  }
}  

这是个递归的算法，相当简单，从排列最原始的想法开始，递增的填一个数，然后拼接剩下的数的排列，。这里填数需要一个类似分配的方法，所以叫做alloc,就是当前过程中还没用上的数,并且大于传入的参数以获得递增的去拿这些数。alloc的实现可以非常蠢，比如，标记所有已经用过的，然后从头走到尾，得到一个没用过的并且大于参数的结果。

第一个算法从第一个排列开始，第二个算法在第一次回朔之前也会到达这个状态，OK,第一个排列成功产生。 对于算法过程中任何一次回朔，第二个算法的执行的规律是：free掉这个数，回到上一次，这时候free掉的数将会被分配器回收，然而，如果上次尝试去alloc下一个数的时候，必须刚才free的比他目前所用的大，否则，他还得乖乖的free他的数，再回到上一次，一直进行下去。这是显然的。于是，第一个算法的第2步得到解释：获取一个能增长的a[j]，他的条件很简单：a[j] < a[j + 1].

我们找到了a[j],我们要从那个愚蠢的分配器中alloc一个新的数，在上次的回朔中，除了找到a[j]，还得到一个结果,a[j + 1] >= a[j + 2] >= ... >= a[n].有序的。这些数都被free而回收在分配器中，那么a[j]去调用alloc的结果就是从这一批数中得到那个最小的但是比a[j]大的数，所以第一个算法的第3步得到解释。a[l]就是alloc的结果。

这时候，第2个算法又要继续增加递归的深度了，很显然，a[j]增长了，接下来a[j + 1]...a[n]将从分配器中alloc到新的结果,显然，他们会是从小到大的顺序被分配，第一个算法的第4步讲得到这个分配到下次回朔之前的结果，也就是得到下一个排列的结果。那么排序就是了，不过这时候不需要冒泡也不需要快排，因为刚刚free的a[j]和a[l]交换之前是有序的：并且：

  a[l + 1] < a[l] < a[l - 1] 
  a[l + 1] < a[j] < a[l]         a[l]需要是比a[j]大的最小的数
所以
  a[l + 1] < a[j] < a[j - 1]

这意味着交换后这个本来是单调降序的依然保持着这个降序。这样重新排序为升序就是不断交换前后，老大变老末，老2变老末2。

这样，一个蠢算法就是相当于行动上证明了一个好算法。