要说起来当年为什么会喜欢上编程这个东西的话，一直追根溯源的话，那应该是当时刚学编程没过半个月的时候，大概才一周多一点，刚学会一些简单的基本语法，写函数什么的，然后忘了因为什么原因，反正拿到了网上别人的一份代码，代码实现的是1~n的全排列输出，当时我自己先写过，但是由于对递归还没什么概念，所以基本写不出来，而那份代码显然，使用递归写的，第一次见到递归啊，我当时还傻傻的一步一步自己像电脑一样走了一遍流程，越看越觉得尼马这玩意儿太神奇了【虽然现在自己随手就能写那种程序。。】，简直就是思维高度浓缩出来的结晶。。。。嗯，大概，就是因为那份代码，所以喜欢上变成了吧。。。

好吧，还是扯远了，回到主题，最近又去图书馆随手借了一本以前没看过的算法书，看看有啥好玩的东西，然后就看到了一章将全排列输出的，然后就想到了上面那一段。。。不过我们这次讲全排列输出，一种最简单最基本最容易想到的全排列输出方案就是采用所谓的减治法，我们为了得到1~n个数的全排列输出，我们可以再得到其中的n-1个数的全排列的基础上，把最后的一个数插入到n-1个数的排列的中减去，说白了，写一个简单的递归函数就可以啦~

比如一开始我们有第一个数1；

然后把2插到各个位置，就得到了21,12

然后把3插到21的各个位置，得到321,231,213

把3插到12的各个位置，就得到312,132,123

然后无尽下去。。。

虽然这个算法简单，容易理解，但是其实编起程序来，就会发现递归的堆栈会随着N的增加逐渐以n！增长，可能还没输出全部，堆栈就爆了。。。

然后发现了一个很好玩的算法，RT所示，所谓的Johnson-Trotter，虽然这个算法理解为什么可以完成这个任务上好像不是很好理解的样子，至少不是那么直观，但是，他就是可以，而且流程很简单，编起程来很快的。

这个算法是怎么做的呢？首先它给每个要排列的数增加了一个方向，左或者右，然后我们再定义一个概念，如果一个数它的箭头所指向的那个方向的邻居那个数比他小，那么我们称这个数是”可移动的“，比如一个数的方向指向左，左边那个数比它小，那么它就是可以移动的；

然后下面就是算法的流程：

1. 初始化一个序列为1,2,3,4,5…n,并且方向全部向左，然后输出这个序列
2. 如果序列存在”可移动的”数，转3，否则，退出
3. 找到最大的那个可移动的数k
4. 把这个数和它所指向的方向的那个邻居交换
5. 所有比k大的数的方向全部反转
6. 输出序列
7. 跳转到2

嗯，就是这样；

编程实现起来有什么好处呢？我们可以直接一个while语句，每执行一次while语句里面的东西就可以输出一个序列，因为不是递归，所以堆栈绝对不会因为n过大而爆掉。。

这个算法的输出结果确实不太直观，比如说最后一组输出是2134，为毛是2134啊，你何德何能，有啥特点可以作为最后一组输出的结果啊，是吧，如果你是4321那我就认了。。。

而且这个算法一个问题还在于，我们很难根据中间输出的某一个序列，就马上推断出下一个序列是什么，也就是所谓的输出结果让人感觉很”别扭”！！

我之前为了观察这个输出结果的变化规律，还专门把1,2,3,4这四个数字的位置变化用红色标记出来【当然使用代码跑出来的。。】，如下面所示，再怎么看。。。也实在看不出个啥来啊。。。

其实倒也不是说完全没规律，只是”乍看”只下很难发现规律而已。。。

假设我们已经通过一开始说的那种方法得到了123的全排列序列：

  123，132，312，321，231，213

然后再把4给插进去，得到：

1234    1324   3124   3214   2314   2134
1243    1342   3142   3241   2341   2143
1423    1432   3412   3421   2431   2413
 4123    4132   4312   4321   4231   4213

然后请你一列一列竖着按蛇形(所谓S形)走一遍，嗯，懂了？

我也不知道这个算法一开始是不是在这样的基础上，抽象出个方向这种概念出来得到的，如果是，我想说：这是我的膝盖，请收下！！

然后下面是matlab代码，不过这里有两点要说明一下：

1. 下面的代码看起来可能没有我上面写的流程那么直观，因为本着”代码至简”的原则，做了一些小手术【但是我实现的确实是上面的算法！！】，比如序列左右各增加了一个Inf(无穷大)的数作为保护壁，可以避免数组越界问题，不然又要加for语句和if判断，这样代码更难看。。还有就是利用matlab语言的特点，在交换那里面用了点数学上的抽象。。
2. 其实这样算来，核心代码很短的，代码里面注释那一块是为了输出上面的那几幅图，唉，没办法，这个博客不方便在文字上面大箭头，所以上面的那几个结果都是图片，而这个图片的输出方式就是matlab输出Latex的代码，然后再用Latex显示输出。。。。
3. 哦，对了再说一句，其实利用这个算法，可以很方便的输出格雷码的~

Code：

function Johnson_Trotter()
clc;
N = 4;
list = [Inf 1:N Inf];

%-1->Left   1->Right
Arrow = [Inf ones(1,N)*-1 Inf];

Largest_Mobile = GetLargestMobile(list,Arrow);
while(Largest_Mobile ~= -1)
    idx = find(list == Largest_Mobile);
    BoolR = (1 == Arrow(idx));
    %换位
    list = [list(1:idx-2+BoolR) list(idx+BoolR) list(idx-1+BoolR) list(idx+1+BoolR:end)];
    Arrow = [Arrow(1:idx-2+BoolR) Arrow(idx+BoolR) Arrow(idx-1+BoolR) Arrow(idx+1+BoolR:end)];
    %大于可移动最大值的全部改方向    
    Arrow(list>Largest_Mobile) = -Arrow(list>Largest_Mobile);
    Largest_Mobile = GetLargestMobile(list,Arrow);
end

% function DisplayResult_ForLatex(list,Arrow,Largest_Mobile)
% str = '$';
% for i = 2 : length(list)-1
%     if(list(i) == Largest_Mobile)
%         str = [str '\textcolor[rgb]{1.00,0.00,0.00}{'];
%         if(Arrow(i) == -1)
%             str = [str '\overleftarrow{'];
%         else
%             str = [str '\overrightarrow{'];
%         end
%         str = [str num2str(list(i)) '}}'];
%     else
%         if(Arrow(i) == -1)
%             str = [str '\overleftarrow{'  num2str(list(i)) '}'];
%         else
%             str = [str '\overrightarrow{'  num2str(list(i)) '}'];
%         end
%     end
% end
% str = [str '$\par'];
% disp(str)

function Largest_Mobile = GetLargestMobile(list,Arrow)
Largest_Mobile = -1;
for i = 2 : length(list)-1
    if( list(i) > list(i+Arrow(i)) && list(i) > Largest_Mobile)
        Largest_Mobile = list(i);
    end
end
disp([num2str(list(2:end-1))]);
% DisplayResult_ForLatex(list,Arrow,Largest_Mobile)

【完】

本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com