用插孔法来找数字的全排列，该用什么算法来实现呢？

举个例子，已经知道123的全排列是 123 132 213 231 312 321
想求1234的全排列，对123来讲，它有四个空隙可以插入数字4，出来的结果是4123 1423 1243 1234
同样对132 213 。。。。。321做相同的处理， 就可以得到N=4时的全排列了


只是这个算法该怎么写呢？
想用个递归调用，可是感到是老虎吃天，无从下爪啊！

多谢

辛苦了，谢谢卧龙了

我比较不清楚的地方就是这个函数的调用，刚才我是给你举个例子，就是说已知3的全排列，求4的全排列

我想做的是，求N的全排列。方法是用N来递归调用（N-1）的全排列，N-1调用N-2。。。，一直到N=2，全排列为12 21；


问题就出现在，这里面N 与N-1都是一个变量，如果用数组来实现的话，而数组的长度必须是定直的，不能随着变量的更改而更改

伪代码如下：
num(N)
{if N==2 生成一个2维数组，里面是 1 2 2 1};
N>=2 则调用num(N-1) 根据num(N-1) 来构造出num(N)这个数组}


实际实现的时候，就是这个数组的长度是不确定的，而用链表则插入起来太麻烦了

}

哦，多谢