白话算法(7) 生成全排列的几种思路(三) 临位对换法

可以直觉地知道，只要把数组任意相邻的两个元素交换位置，就可以得到一个新的排列。例如把数组 [1,2,3,4,5] 的 5 和 4 交换位置就得到 [1,2,3,5,4]，再把 5 和 3 交换位置就得到[1,2,5,3,4]……这样不停地交换就能得到所有的（不重复的）排列吗？这里有两个问题：
　　1）怎么知道交换相邻的两个元素就能得到所有的排列（还是说有时候也需要交换不相邻的元素）？
　　2）要以何种顺序交换元素才能保证每次都得到新的（不重复）的排列呢？
把5依次与前面的4、3、2、1交换位置其实等于把 5 插入到子数组 [1,2,3,4] 的所有可能的位置上得到新的排列。如果我们事先已经知道子数组 [1,2,3,4] 的所有排列，就可以把 5 插入到这些排列的所有可能的位置上得到数组 [1,2,3,4,5] 的所有排列。那么如何知道子数组 [1,2,3,4] 的所有排列呢？我们同样可以把 [1,2,3,4] 分解为 4 和子数组 [1,2,3]……这样一直分解到子数组只剩一个元素时为止。按照这个思路，我们将得到一个普通的递归生成全排列的算法。不过临位对换法使用的是另一种思路：为每个元素附加一个移动方向。

view sourceprint?class Item 

{ 

    public Item(string value, Item[] container, int index) 

    { 

        Value = value; 

        Direction = ItemDirection.Left; // 初始时方向默认指向左边 

    } 

    // 元素的值 

    public string Value { get; set; } 

    // 元素的移动方向 

    public ItemDirection Direction { get; set; } 

} 

enum ItemDirection 

{ 

    Left = 0, 

    Right = 1 

}

有了这个移动方向之后，临位对换法的规则就变得极其简单了：
　　1）如果一个元素的移动方向所指向的那个临位比它小，此元素就是可移的；相反，如果一个元素的移动方向所指向的那个临位比它大，此元素就是不可移的。如果一个元素的移动方向上没有临位，此元素也是不可移的。
　　2）每次都是先寻找最大的可移元素 max，把它与移动方向所指向的那个临位交换，然后把所有比 max 大的元素的移动方向反转。
　　3）不断重复(2)，直到所有元素都不可移为止。
下面演示数组 [1,2,3,4,5] 使用临位对换法生成前 27 个排列的过程。

源码如下。

view sourceprint?class Program 

{ 

    static void Main(string[] args) 

    { 

        string[] source = new string[] { "1", "2", "3", "4", "5" }; 

        foreach (IList<string> p in SwapPermutation(source)) 

        { 

            Console.WriteLine(p.Montage(t => t, " ")); 

        }  

    } 

    // 使用临位对换法生成全排列 

    static IEnumerable<IList<string>> SwapPermutation(string[] source) 

    { 

        yield return source.ToList(); // 第一个排列就是数组的初始顺序 

        LinkedList<Item> s = Item.Create(source); // 初始化 

        Item max = null; 

        while ((max = FindMaxMovableItem(s)) != null) // 寻找最大的可移元素 max 

        { 

            max.Move(); // 把 max 与移动方向所指向的那个临位交换 

            yield return s.ToList(t => t.Value); // 交换后产生了一个新的排列 

            // 把所有比 max 大