问题

遇到一问题：“重名的问题中外都有，例如：搜索 Michael Smith： http://academic.research.microsoft.com/Search.aspx?query=michael%20smith 你可以看到有很多 Michael Smith,  同时还有Mike 的拼写, 不同的 middle name 等问题。 每篇论文提供的作者，单位信息也不一样怎么办?”

看到这个问题，我觉得根源可以描述为：从网上扒下m篇文章，其中可以抽取n个作者名字出来，现在需要确定哪些作者名字是指的同样一个人（合并问题）？

难点一：作者单位关系演变历程

例如： Michael David Smith 的 Affiliation history 可能是：

· Stanford University
· Harvard University
· University of Alberta
· University of Calgary
· Carnegie Mellon University

同一个作者，可能在很多单位发表过论文，如何识别出每个作者的单位关系演变历程？

难点二：名字多种写法

例如：Michael David Smith 也可能是 Michael D. Smith 或者其他拼写

对于非英语国家的作者，名字可能在文章中出现多种可能，例如：中文刊物发表的文章叫“张三”，英文的叫“ZhangSan”，或者直接是其他英文名。

难点三：文献信息不全

如果文献包含了作者简介，还比较好，但是很多只有单位信息。例如：Michael D. Smith 的《A High-Performance Microarchitecture with Hardware-Programmable Functional Units》只有Harvard University, Cambridge

信息来源

在思考方法之前，应该先考虑解决这个问题的信息来源：

1. 作者单位信息。一般来说，每个能找到作者的文章都有单位信息，但是有上述“演变问题”。
2. 作者简介。这个信息量大（性别、出生年月、出生地、单位、研究方向、邮箱、电话等），不也可能存在差异，如描述性差异、语言性差异（中文、英文）
3. 作者个人主页。如果能找到这个，应该能找到挺多信息，如：发表文献列表等。
4. 合作者，例如：通过发掘这些文献，能找出和 Michael D. Smith 一起写过文章的作者：

Glenn H Holloway
Mark A Horowitz
Kartik Hosanagar
Yu Jeffrey Hu
Yu Hu
Fang Huang
Lily Huang  Lily Huang
David S Johnson
Mike Johnson
Mahmut Taylan Kandemir
David Ron Karger
Murali Krishnan
…

5. 作者涉及领域，通过查看作者发表文章，可以推断出作者涉及过的研究领域，例如：Michael D. Smith的研究领域

Microprogram Design Aids,  Microcode Applications,  Memory Structures,  Design Styles,  Cache Memories, Multiple Data Stream Architectures (Multiprocessors) …

 

6. 关键词。可以总结出作者列出过的所有关键词：

code instrumentation
embedded agile methodologies
embedded programming
embedded systems, agile methods, test driven development, tool support
embedded unit
empirical
feature selection
game tree search
general purpose microarchitectures
global instruction scheduling…

    7.   投过的会议、刊物…

初步思路

    初步考虑起来，这个“作者合并”算法应该非常复杂——得先建立作者属性集合，找到最可靠的信息（计算两个作者某些属性的相似度、关联度）进行合并，合并之后更新属性集合，然后继续迭代….

    这个问题貌似会涉及到很多难点，需要更多时间考虑…

另辟蹊径

信息残缺、非结构化，难度很大，我想是否可以通过其他一些手段解决？——

可否无缝整合“学术搜索”、“Word 文献管理”、“Windows Live ID”，“Msn 空间” 等功能？

1. Word中一直缺少强大的“文献管理功能”，现在大家基本都用第三方工具。可否在Word中写文章的时候可以使用类似“Windows Live ID”登录，系统提供通过数据挖掘发现的个人文章，用户可以自行修改（删除不属于自己的）——通过强大方便的文献管理功能吸引大量用户使用，让作者自己完善文献信息？ ？     
2. 在Word中可以直接点击登录到“学术搜索”或者“Msn 空间” 上的“个人学术主页”，包含个人的照片、单位关系历史、发表文献等等一系列信息，方便修改。最好能够整合社交网络的各种功能，例如：人人网、博客、facebook, twiiter等，但是要突出学术交流的特色，提出一些创新功能吸引研究人员。可以学习Web of Science网站 Research ID 提供的那些功能。

期待结果：

1. 如果通过完善自己在“微软学术搜索”上面的主页，能够增加自己文章的引用，能够得到其他作者的提问、评论、反馈，发展成一个比较大的社区，估计信息来源更加准确，搜索结果也会更加准确。
2. 在一个人气社区上面可以建立前面帖子提到的“学术立方”。

问题

教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数
甲说：“我猜不出”
乙说：“我猜不出”
甲说：“我猜到了”
乙说：“我也猜到了”

问这两个数是多少？

分析

初初看这个题目，感觉是他们在说废话～！@#￥%

不过，看过《越狱》的同学应该对这些spy敏锐的眼光，善于抓住线索而赞叹。

运行结果

何不写个程序来推理呢？运行一下得到：

第一个数是3  第二个数是4

第一个数是3  第二个数是6

解法

for (int i = 2; i < 10; i++)

    for (int j = i; j < 10; j++)

    {

        var sums = DecomSum(i + j);

        if (sums.Count < 2) continue;

       //如果不满足第一个条件——甲说不知道 => 他得到的数可以分解为多个“数对”相加

        var products = DecomProduct(i * j);

        if (products.Count == 1) continue;

       //如果不满足第二个条件——乙说不知道 => 他得到的数可以分解为多个“数对”相乘

        if (!Condition3(sums)) continue;//如果不满足第三个条件——甲说：“我猜到了”

        if (!Condition4(products)) continue;//如果不满足第四个条件——乙说：“我也猜到了”

        Console.WriteLine("第一个数是{0}  第二个数是{1}\n", i, j);

        //Analysis(i, j);

        //Console.WriteLine("\n");

    }

*注：List<Point> DecomSum(int sum) 函数是分解和

       List<Point> DecomProduct(int product) 函数是分解积

再来看其中的函数：

bool Condition3(List<Point> sums)

{

    var unique = 0;

    foreach (var s in sums)

        if (DecomProduct(s.X * s.Y).Count == 1) unique++;

    if (unique == sums.Count - 1) return true;

    return false;

}//甲马上说知道了 => 他得到的数“和分解”出來的多个“数对”的积当中,

只有一个“积分解”是不唯一的,其他都是唯一的

bool Condition4(List<Point> products)

{

    var condition3_satisfied_cnt = 0;

    foreach (var s in products)

    {

        var sums = DecomSum(s.X + s.Y);

        if (Condition3(sums)) condition3_satisfied_cnt++;

    }

    if (condition3_satisfied_cnt==1) return true;

    return false;

}//乙说：“我也猜到了” => 他得到的数“积分解”出来的多个“数对”的和当中，

只有一个的“和分解”满足Condition3

分析

取消其中”分析“代码的注释，得到：

第一个数是3  第二个数是4

分析：
条件一：7可以分解为：3+4,2+5,
条件二：12可以分解为：2*6,3*4,
条件三：
12(=3*4)：
12可以分解为：2*6,3*4,
10(=2*5)：
10可以分解为：2*5,

条件四：
8(=2+6)：
8可以分解为：4+4,3+5,2+6,
7(=3+4)：
7可以分解为：3+4,2+5,

第一个数是3  第二个数是6

分析：
条件一：9可以分解为：4+5,3+6,2+7,
条件二：18可以分解为：2*9,3*6,
条件三：
20(=4*5)：
20可以分解为：4*5,
18(=3*6)：
18可以分解为：2*9,3*6,
14(=2*7)：
14可以分解为：2*7,

条件四：
11(=2+9)：
11可以分解为：5+6,4+7,3+8,2+9,
9(=3+6)：
9可以分解为：4+5,3+6,2+7,

小结

个人觉得这道题目挺有启发的——在生活工作中要保持“把握已知信息的态度”，还是我曾经提到的“能力是一种态度“

看来要多向Micheal Scofiel学习啊…

这个题目涉及到：”组合问题“、”推理问题“、”换位思考“，有点容易晕

刚刚搞定，有空再想想有没问题或者有没更好办法…欢迎大家批评指教

Boyer-Moore算法——“坏后缀规则”？

如前贴所述，BM算法的“好后缀规则”实际上有两种情况：“中缀”和“前缀”。

“前缀”没啥问题，但是我发现“中缀”往往会出现“跳转以后朝向注定的失败匹配”，如下图所示：

如上图，在第6位X处发生了miss match，BM算法会跳转到3位，也就是将pat挪到如上表第三行的样子，再从11位开始比较，假设11～7都匹配成功了，但是X!=B，第6位是注定失败的。

那么可否将“中缀跳表”独立出来，匹配过程中判断”好后缀”加上它的前导字符构成的子串是否在pat中存在？如果不存在就是个“坏后缀”。

例如：上图中的“XXY”实际上是“坏后缀”，而不是“好后缀”，因为在pat中根本不存在这样的子串。

如何考虑“坏后缀规则”？

如果要实现这个规则，需要注意两个问题。

如下图，和前面一样，假设在倒数第三位X处发生了miss match，可以跳转到两个位置（如箭头所示），但是有一个跳转是重复的，A=A。

因此可以看出，如果要独立“中缀跳表”，需要考虑两个问题：

1. 某位置的中缀跳转可能不止一个；
2. 跳转中可能存在重复。如果出现重复，需要取最右边的那个。

很容易想到，满足这两个需求，用个哈希表恰好。

一种实现方法

将（二）贴中的计算中缀跳表的地方用一个函数AddInfixJump(i, j);代替，这个函数如下：

/// <summary>

/// 中缀跳表

/// </summary>

static Dictionary<char, int>[] iJumps;

static void AddInfixJump(int i, int j)

{

    if (j < m - 1)//最后一位采用坏字符移动，这里不需要

    {

        if (iJumps[ j ] == null) iJumps[ j ] = new Dictionary<char, int>();

        //添加中缀跳 能保证从小到大

        if (!iJumps[ j ].ContainsKey(pat[ i ])) iJumps[ j ].Add(pat[ i ], i);

    }

}

这样去计算中缀跳表，能够保证没有重复，并且右边的跳转肯定是先计算的，所以保留的也是最右边的。

然后在搜索过程中，如果在pat倒数第1位以前发生了miss match（也就是不用“坏字符规则”）的时候，先设置跳转为原来的那个表（比原来少了中缀跳转而已），然后再看看是否有好的“中缀”：

shift = mJumps[ j ];//设置为前缀和坏后缀混合跳转

if (iJumps[ j ] != null &&//存在中缀 

    iJumps[ j ].ContainsKey(text[ i ]))//且跳转以后匹配text[ i ]

    shift = m - 1 - iJumps[ j ][text[ i ]];//设置中缀跳 (m-1-j + j-k)

这样能够避免上面出现“注定的失败”了。

实验结果

通过实验我发现，这样改进以后，在随机字符串和英文文章的匹配中，比较次数能够降低10%～30％，但是总体性能提高却不明显。我估计性能肯定是损失在C#的泛型字典Dictionary<>上面了，“坏后缀”的思路应该很好，但是可能需要别的实现方法：比如字符集小的话可以用数组，或者别的语言实现。有人想到好方法麻烦告诉我：）

后记

这和我一直以来的编程经验是相反的：“一般来说，不应该先考虑太细节的优化，算法思想的优化是最重要的”；但是在字符匹配的程序中不完全是这样，字符比较的消耗很小，稍微复杂的逻辑和数据结构都会损失性能，所以凡事都有例外。

有些细节优化却能够提升性能，例如，原版的BM搜索过程是这样的：

var shift = 0;

var k = (int)text[ i ];

if (k < cJumps.Count) shift = cJumps[ k ];

else shift = m;

i += Math.Max(shift, mJumps[ j ]);

贴（二）中，我将其改为：

if (m - j == 1)//末位不匹配

 {

     var k = (int)text[ i ];

     if (k < cJumps.Count) i += cJumps[ k ];

     else i += m;

 }

 else i += mJumps[ j ];

实际上就是当匹配超过1个字符时候，不用去计算“坏字符跳”。这样小改动一点，在随机字符和英文测试中，性能都提高了10％左右。

当然要说明的是，MB算法总体性能相比最原始的BruteForce算法还是有大幅提高的，pat越长越明显。

问题

《编程之美》有一道题目“最短摘要生成”：若输入“微软 亚洲研院 使命”三个关键字，查找最短的摘要：

微软研究院的使命是使未来的 计算机 能够看、听、学，能用 自然语言 与 人类 进行交流。 ... 微软亚洲工程院将以微软亚洲研究院的科研成果为依托，创造关键技术、为微软亚洲研究院核心技术的 孵化 提供有力保证。 ... 微软亚研院的科研环境 编辑本段 回目录…

书中给出的解法是基于“分词”后的数组的。

那么，如果是客户端蜘蛛临时抓的网页，或者是在一堆文件中查找，这时候没有分词、没有建立倒排表，如何直接生成呢？再加上有中英文混杂的情况（查找某种表达的翻译）？

冰山一角

这时我想到了基于“多模式匹配”改进原书中算法，因此决定研究下经典的AC_BM算法。查阅了很多文献后，意外的发现：小小的“字符串匹配”居然有这么多学问～：），引用一段文献——

“String-matching is a very important subject in the wider domain of text processing. String-matching algorithms are basic components used in implementations of practical software existing under most operating systems. Moreover, they emphasize programming methods that serve as paradigms in other fields of computer science (system or software design). Finally, they also play an important role in theoretical computer science by providing challenging problems…”

这段文字出自 http://www-igm.univ-mlv.fr/~lecroq/string/node1.html ，这个网站上竟有35个单模式匹配算法的详细分析、例子、代码、java动画演示…

多模式匹配在：入侵检测、数据挖掘、DNA配对、文本处理（查找替换）等方面都有广泛的应用。

算法发展简要回顾

先简要回顾下经典的AC_BM算法是怎么来的：

1. 1977年，这三个人改进Morris-Pratt 算法提出了Knuth-Morris-Pratt 算法——将“有限状态自动机”＋“递归/递推”思想用得很精妙。

2. 同年，Stanford和Palo Alto研究院的两个人提出了经典的Boyer-Moore算法，主要思想为：

a) 提出了从右往左匹配的思路；

b) 通过“坏字符移动”＋“好后缀移动”避免无谓的比较；

c) “好后缀移动”借鉴了Knuth-Morris-Pratt 算法。

    题外话：这个BM算法就是大家日常“查找替换”时候用的：）

3. 1980年，Horspool简化了Boyer-Moore算法：用实验证明了只采用“坏字符移动”在一般情况下性能足够了。这是因为“好后缀”出现的概率并不大，除非是DNA一类的“小字符集”中的匹配，类似AGTCAAGGTTTC…

4. 1975年，Bell Labs的两个人提出了Aho_Corasick算法，主要思想是构造了“多模式”（多关键字）的“有限状态自动机”（是一棵多关键字树，Knuth-Morris-Pratt 算法是单模式的“有限状态自动机”）

5. 2001年，Silicon Defense的三个人将Aho_Corasick算法和Boyer-Moore算法思想结合起来（因为AC算法没有如BM算法一样很好的跳转，还有优化的空间），就成了AC_BM算法。

由此可以看出，要想搞懂AC_BM算法，得从头一个个来。

引用一个题外话：

AC 算法被用于fgrep1.0（在UNIX中通过-f使用）

BM_AC算法在gre中应用，并被fgrep2.0收用。

Knuth-Morris-Pratt 算法

在单模式匹配中，可把要匹配的关键字看成一个“有限状态自动机”：

例如上图，如要匹配：GCAGAGAG，遇到G就转状态1，再遇到G还是在状态1，遇到C就转状态2… 到8就成功

这个思路挺不错，问题是跳转的条件比较麻烦，于是Morris-Pratt就将其简化为两个：成功s和失败f，如下图所示：

要匹配ABABABCB，成功了就向前，失败了就退回来，再失败了递归退后…如下表：

那么构造的时候可以递推构造，思路挺好：）

那么这个算法最关键就是要构造失败的这些箭头：MP fail links，可以用一个int[]保存。

设要匹配的模式是string pattern; m = pattern.Length; 那么MP fail links可以很简洁地构造：

 int[] Morris_Pratt()
    {
        var fails = new int[m];
        int i = 0;
        int j = fails[0] = -1;
        while (i < m - 1)
        {
            while (j >= 0 && pattern[ i ] != pattern[j]) j = fails[j];
            fails[++i] = ++j;
        }
        return fails;
     }

不知道大家有没发现MP fail links 有个问题，假设遇到：

设要匹配的文本是 string text; 如果text中出现了“…ABAY…”，那么按照MP fail links跳转换过来的还是B（如上表最后一行），肯定匹配不上的，所以Knuth-Morris-Pratt算法就改进了这个问题（将上面while里面改了下），构造KMP fail links：

 ……
while (i < m - 1)
  {
        while (j >= 0 && pattern[ i ] != pattern[j]) j = fails[j];
        i++; j++;
        if (pattern[ i ] == pattern[j]) fails[ i ] = fails[j];
        else fails[ i ] = j;
}
…….

就递推地实现了所有首位字符相同的跳转都合并的效果，如下图所示：

那么在查找的时候，就可以利用 KMP fail links 实现跳转，而且思路和构造的时候类似：

 ……
 int i = index, j = 0;
 while (i < text.Length)
 {
       while (j >= 0 && pattern[j] != text[ i ]) j = fails[j];
       i++; j++;
       if (j == pattern.Length) return i - pattern.Length;//找到
 }

 return –1

后记

今天先写到这里，明天咱们继续研究BM算法，感觉挺巧妙的是利用简短的MP fail links可以找到所有的“中缀”和“后缀”。

需要说明的是，直接利用KMP 搜索效率提高并不明显，因此“查找替换”一般用BM算法。

问题

假设有4×4的方阵（里面可放字符串），给现定一个序列，检查这个序列是否在方阵的“连续对角线”上面：

例如：从左上到右下的连续对角线序列可能是：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16

分析

刚刚看到此题目，可能有点晕，“连续对角线”是啥？仔细一看，其实就是方阵里面的曲线序列（如下图），我就叫它“方曲序列”吧。

再一想，这样的序列应该有8条。考试的时候时间紧，只能大概写写思路了，回来用VS08调试着搞感觉好很多:( 不适合应试哈哈

我们来分析下，这个题目的关键是，要把握住曲线运动其实是两个方向：

1. 沿斜线运动
2. 斜线平移

那么，再看这些斜线的长度分别为 1 2 3 4 3 2 1，那么我们在枚举到这个序列之和的这些关键带点的时候：

1. 需要平移斜线
2. 需要翻转斜线上的运动方向

解法

有了思路，借助VS08 强大的调试功能，我写了8个方向，通用的，O(N)（N是序列长度） 复杂度的 “方曲序列” 函数：

运行函数：PrintWinding(4);

就可以得到 n=4 的时候8条“方曲序列”：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
13 14 9 5 10 15 16 11 6 1 2 7 12 8 3 4
4 3 8 12 7 2 1 6 11 16 15 10 5 9 14 13
16 15 12 8 11 14 13 10 7 4 3 6 9 5 2 1
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16
13 9 14 15 10 5 1 6 11 16 12 7 2 3 8 4
4 8 3 2 7 12 16 11 6 1 5 10 15 14 9 13
16 12 15 14 11 8 4 7 10 13 9 6 3 2 5 1

代码如下：

        static void PrintWinding(int n)
        {
            var square = new string[n, n];
            for (int i = 0; i < square.Length; i++)
                square[i / n, i % n] = (i + 1).ToString();

            var p = new int[] { 0, n - 1 };
            for (int sign = -1; sign <= 1; sign += 2)
                for (int i = 0; i < p.Length; i++)
                    for (int j = 0; j < p.Length; j++)
                        PrintWinding(square, p[ i], p[j], sign);
        }

其中：

        static void PrintWinding(string[,] square, int x0, int y0, int sign)
        {
            int n = square.GetLength(0);//边长

              int xn = Math.Abs(x0 - n + 1);//目标点x
            int yn = Math.Abs(y0 - n + 1);//目标点y

            int dx = Math.Sign(xn - x0);//平移方向x增量
             int dy = Math.Sign(yn - y0);//平移方向y增量

             int stepX = -dx * sign;//斜线方向x增量
             int stepY = dy * sign;//斜线方向y增量

             int flag = sign == 1 ? 0 : 1;

            int x = x0, y = y0;
            int s = 1, k = 1, sum = 1;
            for (int i = 0; i < square.Length; i++)
            {
                Console.Write(square[y, x] + " ");

                if (i + 1 < sum)
                {
                    x += stepX;
                    y += stepY;//沿斜线方向移动
                  }
                else if (i + 1 == sum)
                {
                    stepX *= -1;
                    stepY *= -1;//斜线方向掉头

                      if (k == n) flag = Math.Abs(1 - flag);

                   if ((k & 1) == flag) x += dx;//平移
                      else y += dy;//平移

                     if (s < n) k++;//前半三角
                     else k--;//后半三角

                     sum += k;
                   s++;
                }
            }
            Console.WriteLine();
        }

讨论

有了8个方向，通用的“方曲序列” 函数，我们就不难写出测试某序列是否在”连续对角线“上面的函数了，可以考虑采用PLINQ写个并行算法，多个核的话每个核测试一个（些）方向的序列，找到就返回true。

问题

在开发过程中常常需要处理集合，因此我写了一些常用算法，贴出大家提提意见。

本帖介绍幂集合生成算法。

解法一

思路为：

1. 构造初始序列00…0
2. 如果全部为11…1，则停止
3. 寻找位置最低的0，将其变1
4. 将刚刚那个0前面的都变0

这里可以用到前面帖子构造的“动态有序集合”——BinHeap，共设置两个：一个用于保存0的位置，一个用于保存1的位置：

    public static List<T[]> Subset<T>(IList<T> list)
        {
            var zeros = new BinHeap<int>(false);//0的位置集合（因为不需要建立索引，传入false)
            var ones = new BinHeap<int>(false);//1的位置集合

            List<T[]> subsets = new List<T[]>();
            for (int i = 0; i < list.Count; i++) zeros.Push(i);//初始状态全0

            while (ones.Count < list.Count)
            {
                var i = zeros.Pop();
                while (!ones.IsEmpty && i > ones.Peek()) zeros.Push(ones.Pop());
                ones.Push(i);

                i = 0;
                var arr = new T[ones.Count];
                foreach (var p in ones) arr[i++] = list[p];
                subsets.Add(arr);
            }
            return subsets;
        }

运行结果

输入abcde，得到2^n – 1 个子集：

1:a  2:b  3:ab  4:c  5:ac  6:bc  7:acb  8:d  9:ad  10:bd  11:adb  12:cd  13:adc 14:bdc  15:abcd  16:e 

17:ae  18:be  19:aeb  20:ce  21:aec  22:bec  23:abce  24:de  25:aed  26:bed  27:abde  28:ced  29:acde  30:bcde  31:abdec

讨论

这里也没有用一般算法的“扫描”的办法，而是利用的两个“动态有序集合”解决了问题，效率提高很多。

解法二

当然，这个问题也肯定可以用前面连载里面广泛用到的“分级排列（组合）法”。

    public static List<T[]> Subset2<T>(IList<T> list)
        {
            List<T[]> subsets = new List<T[]>();
            var heap = new List<T[]>[list.Count + 1];//0～n级的组合

            for (int i = 0; i < heap.Length; i++) heap[ i ] = new List<T[]>();
            heap[0].Add(new T[0]);

            for (int i = 0; i < list.Count; i++)
                for (int j = i + 1; j > 0; j--)
                    foreach (var p in heap[j - 1])
                    {
                        var subset = new T[p.Length + 1];
                        p.CopyTo(subset, 0); subset[p.Length] = list[ i ];
                        heap[j].Add(subset);//更新j级

                         subsets.Add(subset);
                    }
            return subsets;
        }

运行结果

1:a  2:ab  3:b  4:abc  5:ac  6:bc  7:c  8:abcd  9:abd  10:acd  11:bcd  12:ad  13:bd  14:cd  15:d  
16:abcde  17:abce  18:abde  19:acde  20:bcde  21:abe  22:ace 23:bce  24:ade
 25:bde  26:cde  27:ae  28:be  29:ce  30:de  31:e

可以看出，顺序稍微有些差异，但结果相同，解法二效率稍高。

问题

在开发过程中常常需要处理集合，我写了一些常用算法，贴出大家提提意见

本帖是最简单的全排列生成算法，因为全排本来列就很费，所以以简洁为重，没太多考虑效率。

解法

        public static List<T[]> Permutation<T>(IEnumerable<T> list)
        {
            List<T[]> permutations = new List<T[]>();

            Permutation(new List<T>(list), 0, permutations);

            return permutations;
        }
        static void Permutation<T>(List<T> list, int h, List<T[]> permutations)
        {
            if (h == list.Count - 1)
            {
                permutations.Add(list.ToArray());
                return;
            }

            for (int i = h; i < list.Count; i++)
            {
                Swap(list, h, i);
                Permutation(list, h + 1, permutations);
                Swap(list, h, i);//撤销交换

              }
       }
        static void Swap<T>(List<T> list, int i, int j)
        {
            if (i != j)
            {
                var temp = list[ i ];
                list[ i ] = list[j];
                list[j] = temp;
            }
        }

运行结果

输入abcd：

1:abcd  2:abdc  3:acbd  4:acdb  5:adcb  6:adbc  7:bacd  8:badc  9:bcad  10:bcda  11:bdca  12:bdac  13:cbad  14:cbda  15:cabd  16:cadb  17:cdab  18:cdba  19:dbca 20:dbac  21:dcba  22:dcab  23:dacb  24:dabc

讨论

算法思路很简单，就是一位一位去填，和全排列计算的思路一致。

此算法在只需要输出或者测试排列的问题中，可以不去生成所有排列的实例，从而节约大量内存。