产生n个数全排列的算法

2024-09-14 07:50:13

给定n个数{1...n},如何给出这n个数的全排列呢？

给定一个整数k，我们给它一个向左或向右的方向,k(->)或者k(<-),我们说k是可以移动的，如果它的方向指向一个相邻的比它小的数，例如

2(->)6(->)3(->)1(<-)5(->)4(->)

那么只有3,5,6是可以移动的。

全排列的算法如下：

从1(<-)2(<-)...n(<-)开始

当存在一个可以移动的数时，

(1)找到最大的可以移动的数m

(2)交换m和它的方向指向的相邻的数

(3)对所有满足p>m的p,改变所有p的箭头方向

例如当n=3时：

1(<-)2(<-)3(<-)

1(<-)3(<-)2(<-)

3(<-)1(<-)2(<-)

3(->)2(<-)1(<-)

2(<-)3(->)1(<-)

2(<-)1(<-)3(->)

最新文章

热门文章