next_permutation 算法原理和JS实现

C++ STL中的 next_permutation 函数和 prev_permutation 两个函数提供了对于一个特定排列P,求出其后一个排列P+1和前一个排列P-1的功能。

我们假设一个序列Pn=<3 6 4 2>,我们可以从右起第一位看成各位,第二位为十位以此类推,那么很容易得出递减序列表示的数最大,这个例子中<6 4 2>为递减,已经无法通过交换数字位置得到更大的数,所以我们找到第一个非递减元素3,然后从前面递减序列中找到第一个大于它的元素4,交换着两个元素得到<4 6 3 2>,但是这里<6 3 2>仍是递减,而我们需要以4开头的最小序列,所以我们还要将递减序列颠倒成递增序列,最终得到Pn+1=<4 2 3 6>。

算法步骤如下:

  • 从尾端向前,找到两个相邻元素 i < (i+1)
  • 再从尾端向前,找到第一个元素满足 j > i
  • swap(i, j), 然后把 i+1 之后的所有元素 reverse 倒排
#include<cstdio>
#include<cstring>

void inline swap(char *s1,char *s2){
    char t=*s1;*s1=*s2;*s2=t;
}

//反转字符串函数,s,e分别执行字符串的开始和结尾
void reverse(char *s,char *e){
    for(e--;s<e;s++,e--)swap(s,e);
}

bool next_permutation(char *start,char *end){
    char *cur = end-1, *pre=cur-1;
    while(cur>start && *pre>=*cur)cur--,pre--;
    if(cur<=start)return false;
    
    for(cur=end-1;*cur<=*pre;cur--);//找到逆序中大于*pre的元素的最小元素 
    swap(cur,pre);
    reverse(pre+1,end);//将尾部的逆序变成正序 
    return true;
}

JS实现:

function next_permutation( arr ) {
    const length = arr.length;
    if( length <=1 ) return false;
    
    let i = length;
    while(true){
        var t = i;
        i--;
        if( arr[ i ] < arr[ t ] ) {
            var j = length;
            while( !( arr[ i ] < arr[ --j ] ) );

            const temp = arr[ i ];
            arr[ i ] = arr[ j ];
            arr[ j ] = temp;
            
            // splice()函数做了两件事,首先将arr的t以后的元素移除,并且将移除的部分颠倒后保存在rev中
            var rev = arr.splice( t, length ).reverse();

            // 将后面颠倒后的部分连接至arr,这里不能用concat()来连接,否则改变的就不是原来的arr了
            Array.prototype.push.apply( arr, rev );
            return true;
        }
        if(!i){
            arr.reverse();
            return false;
        }
    }
}

红黑树

红黑树在C++的STL中很广泛,例如map和set都是用红黑树实现的,此外还大量应用在Linux系统中。所以有必要深入了解下。

定义

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树的基础上增加了以下要求:

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色(叶子是NIL节点)。
  • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

插入

先把结点标记为红色,再按二叉查找树的方法插入,最后再根据红黑树的要求进行调整。
所以我们根据插入后被破坏的红黑树性质进行分情况讨论。

  1. 被插入节点是根结点直接涂黑
  2. 被插入节点的父根结点为黑色,那么插入后的新树仍然是一棵红黑树
  3. 被插入的节点的父节点是红色,那么我们调整的最终目标是将这两个红色层层上移动,最终通过旋转将其中一个红色移动到最顶端,然后将其涂黑(注意不节点移动,只是颜色自下而上传递)

Case 1 当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。
(01) 将“父节点”设为黑色。
(02) 将“叔叔节点”设为黑色。
(03) 将“祖父节点”设为“红色”。
(04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

Case 2 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子
(01) 将“父节点”作为“新的当前节点”。
(02) 以“新的当前节点”为支点进行左旋。

Case 3 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子
(01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”。
(03) 以“祖父节点”为支点进行右旋。

为何将插入节点置为红色?
选黑色不是不可以,调整嘛,最终总是能符合定义。首先我们插入操作对之前的红黑树造成的破坏只可能有2.4.5,当我们选择红色的时候永远不会违反性质5,所以置为红色比黑色要简单。

与AVL树比较

  1. 如果插入引起了树的不平衡,AVL和红黑树都是最多只需要2次旋转操作,即两者都是O(1);但是在删除引起树的不平衡时,最坏情况下,AVL需要维护从被删节点到根这条路径上所有节点的平衡性,因此需要旋转的量级O(logN),而红黑最多只需3次旋转,只需要O(1)的复杂度。
  2. AVL的结构相较RB-Tree来说更为平衡,所以在插入和删除node更容易造成不平衡,因此在大量数据需要插入或者删除时红黑树效率更高。