白话算法(7) 生成全排列的几种思路(一)
我在黄昏时坐在地球上
我这样说并不表明晚上
我就不在地球上
——海子 《明天醒来我会在哪一只鞋子里》
思路1：加大搜索空间，使用评估函数找到解
“如果在可能的地方找不到，就去不可能的地方找。”这是一句废话，也是一句挺有道理的话，甚至有时候，它还是一句有用的话。因为生活中有时真的会有神奇的事情发生。元宵节的前一天晚上，我和一位同事加班到10点半，正准备回家的时候，突然发现大事不妙——办公室唯一的一把钥匙找不到了——没有钥匙就没办法锁门，我们回不去家了。办公室是客户借给我们的，备份钥匙只有客户有，但是这么晚了实在不好意思打电话求救。钥匙是我几个小时前放在同事的桌子上的，却不知被同事随手扔到哪里去了。桌子上，抽屉里，所有的包包和衣服兜全找过了，就是不见钥匙的踪影。现在我们有3种选择：1）放弃。在办公室里睡到天亮或者不锁门就回家（但是那一屋子的电脑还有服务器实在让人放心不下）；2）再找一遍。不过已经找了2遍了，再原样重复一遍结果也不会有什么改变。3）去不可能的地方找。我决定碰碰运气。结果，5分钟之后，我居然在桌子上一个装着汤圆的袋子里找到了那把已经冻得冰凉的钥匙。
如果没办法直接取得沙子里的金子，就把沙子和金子一同捞起来，再用水慢慢淘去沙子，留下砂金。如果没有办法直接求解，可以先找到一个虽然大一些但是比较容易取得的包含所有解的搜索空间，再使用评估函数判断搜索空间里每一个潜在解的质量。
现在我们想求得["a","b","c"]的全排列，也就是想要得到解（为了看着舒服省略了引号）：
[[a,b,c],
[a,c,b],
[b,a,c],
[b,c,a],
[c,a,b],
[c,b,a]]
数组的下标的排列是：
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
有没有什么方法可以由“0 1 2”经过某种计算得到下一个下标的排列“0 2 1”呢？如果把 012 看作是一个3进制的数字，那么把 012 加 1 就得到了 021。但是，把 021 加 1 得到的是 022 而 不是 102。所以，用这种方法比较容易得到可重复的排列，从000开始，每次增加1可以得到：
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
其中绿颜色表示的是我们想要的结果，我们只要把它们挑出来就好。
如果把 currentIndexList 看作是一个 currentIndexList.Count 进制的数字，GetNextIndexList() 函数的作用是把这个数字增加1：
html#viewSource" highlighterId="highlighter_841650" commandName="viewSource">view sourceprint?
static void GetNextIndexList(IList<int> currentIndexList) |
int count = currentIndexList.Count; |
for (int i = count-1; i >= 0; i--) |
if (currentIndexList[i] < count - 1) |
