问题

给定一个递增序列
其中，，若，则。求它的递增全排列集合。

所谓递增全排列是这样一个有序集合：
其中是序列的一个全排列，并且，都有，表示的自然顺序大于。例如，对于递增序列，都是它的一个全排列，且的自然顺序大于。
显然，对于，一定有，。

分析

设
我们定义加法运算表示两个序列的拼接。例如，若，，则

那么，自然可以定义一个序列与一个有序集合的加法运算

这个式子进一步可以用求和符号简化为

现在考虑函数，由于其产生一个递增全排列集合，显然前项全排列的第一个元素是，第到第项全排列的第一个元素都是，……，第到第项的第一个元素都是。这就意味着

由于剩余的序列仍然是有序的，因此对剩余的个序列产生递增的全排列集合就成为该问题的子问题，我们使用递归定义了它们。

现在考虑最基本的情况：

1. 序列没有任何元素，显然
2. 序列只有一个元素，显然，即一个元素的全排列只有一种，就是它本身。

由此我们可以得到产生递增的全排列集合的算法。

算法

• 输入：一个有限的递增有序序列
• 输出：序列递增全排列集合

1. 初始化结果集。
2. 若序列中仅有一个元素，或为空（此时），则，算法结束，返回。
3. 否则，分别令，对于，递归地使用该算法计算剩余的有序序列的递增全排列集合，令，由此我们得到了以为固定首位的全排列集合。从而归并到结果集合中。
4. 由于中元素是有限的，所以算法的递归过程一定会到达2中的状态并终止，从而算法在有限步骤后一定会终止。

代码

使用JavaScript实现的代码如下

function generatePermutation(n){
    let seq=(length=>Array.from({length},($,i)=>i+1))(n),result=[];
    //Require substring of seq starting from start is a rigidly-ascending ordered sequence,
    //namely, for any i,j with start<=i<j<length, seq[i]<seq[j] holds.
    (function permutation(seq,result,start=0){
        //recursive function for all permutations of seq with a specified start index(counting from 0).
        //The permutation of single element is this element itself, so stop here.
        start===seq.length-1 && result.push(Array.from(seq));

        //Now,we can get all permutations by the following: 
        //  Permutation(<a1,a2,...,an>)
        //  =SUM_[from i=1 to n] ( ai + Permutation(<a1,a2,...,a_{i-1},a_{i+1},...,an>) )
        //  where a1<a2<...<an, and notation <...> stands for an ordered sequence.
        for(let i=start;i<n;i++){
            // to achieve this, we can move ai to the head, leaving the remnants,say,
            // <a1,a2,...,a_{i-1},a_{i+1},...,an> ,still ordered. Thus, we apply permutation
            // on these remnants, which turns to be a subproblem. 
            // NOTICE: if ascending ordered permutations are required, we use function move.
            // Otherwise, a simple swap can be used here.
            // 
            move(seq,i,start);      //swap(seq,i,start);
            permutation(seq,result,start+1);
            move(seq,start,i+1);    //swap(seq,i,start);
        }
    })(seq,result);
    return result;
}

//move seq[from] to before seq[to]
function move(seq,from,to){
    [[to,0,seq[from]],[from+(from>to),1]].forEach(arr=>seq.splice(...arr))
}

// swap seq[i1] with seq[i2]
function swap(seq,i1,i2){
    [seq[i1],seq[i2]]=[seq[i2],seq[i1]];
}

generatePermutation(4)

为了保证剩余序列的有序，使用move函数将a_i元素移动到数列的首位，此时对剩余序列（start=start+1开始的下标）进行递归排序。

注意，代码中还提供了一个交换函数swap，如果将generatePermutation中的move替换为swap，那么产生的结果集合仍然是全排列集合，但是它不是有序排列的集合。