白话算法(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]……这样一直分解到子数组只剩一个元素时为止。按照这个思路，我们将得到一个普通的递归生成全排列的算法。不过邻位对换法使用的是另一种思路：为每个元素附加一个移动方向。

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 个排列的过程。

源码如下。

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 大的元素的移动方向反转
            foreach (Item item in s)
            {
                if (item > max)
                    item.ReverseDirection();
            }
        }
    }

    // 寻找最大的可移元素，找不到时返回null
    static Item FindMaxMovableItem(LinkedList<Item> s)
    {
        Item max = null;
        foreach (Item item in s)
        {
            if (item.IsMovable() && (max == null || item > max))
                max = item;
        }
        return max;
    } 
}

Item的完整代码如下。

// 带有方向的元素
[DebuggerDisplay("Value = {Value} Direction={Direction} Index = {Index}")]
class Item
{
    public Item(string value)
    {
        Value = value;
        Direction = ItemDirection.Left; // 初始时方向默认指向左边
    }
    // 元素的值
    public string Value { get; set; }

    // 元素的移动方向
    public ItemDirection Direction { get; set; }

    // 在链表中的节点
    public LinkedListNode<Item> Node { get; set; }

    // 初始创建
    public static LinkedList<Item> Create(string[] source)
    {
        LinkedList<Item> result = new LinkedList<Item>();
        for (int i = 0; i < source.Length; i++)
        {
            Item item = new Item(source[i]);
            // 增加对链表中节点的反向引用，以便能够知道前一个和后一个节点是什么
            item.Node = result.AddLast(item); 
        }
        return result;
    }

    // 反转元素的移动方向
    public void ReverseDirection()
    {
        if (Direction == ItemDirection.Left)
            Direction = ItemDirection.Right;
        else
            Direction = ItemDirection.Left;
    }

    // 返回元素是否可移
    public bool IsMovable()
    {
        // 如果一个元素的移动方向所指向的那个邻位比它小，此元素就是可移的；
        // 相反，如果一个元素的移动方向所指向的那个邻位比它大，此元素就是不可移的。
        // 如果一个元素的移动方向上没有邻位，此元素也是不可移的。
        if (Direction == ItemDirection.Left) // 移动方向向左时
        {
            if (Node.Previous == null) // 已经是最左侧元素时
                return false;
            else
                return Node.Previous.Value < this;
        }
        else // 移动方向向右时
        {
            if (Node.Next == null) // 已经是最右侧元素时
                return false;
            else
                return Node.Next.Value < this;
        }
    }

    // 与移动方向所指向的那个邻位交换
    public void Move()
    {
        if (Direction == ItemDirection.Left) // 移动方向向左时
        {
            // 与左侧元素交换位置
            Item temp = Node.Previous.Value;
            Node.Previous.Value = this;
            Node.Value = temp;

            temp.Node = Node;
            Node = Node.Previous;
        }
        else // 移动方向向右时
        {
            // 与右侧元素交换位置
            Item temp = Node.Next.Value;
            Node.Next.Value = this;
            Node.Value = temp;

            temp.Node = Node;
            Node = Node.Next;
        }
    }

    public static bool operator <(Item lhs, Item rhs)
    {
        if (lhs == null || rhs == null)
            return false;
        else
            return lhs.Value.CompareTo(rhs.Value) < 0;
    }
    public static bool operator >(Item lhs, Item rhs)
    {
        if (lhs == null || rhs == null)
            return false;
        else
            return lhs.Value.CompareTo(rhs.Value) > 0;
    }
}
enum ItemDirection
{
    Left = 0,
    Right = 1
}

辅助函数Montage()和ToList()源码如下。

public static class EnumerableExtension
{
    /// <summary>
    /// 将列表元素拼接成由splitter分隔的字符串
    /// </summary>
    /// <example>
    ///     拼接字符串：
    ///         <c>new List<string> { "aa", "bb", "cc" }.Montage(p => p, ","); // 返回："aa,bb,cc"</c>
    ///     拼接对象属性：
    ///         <c>new List<string> { "aa", "bbb", "c" }.Montage(p => p.Length.ToString(), ","); // 返回："2,3,1"</c>
    ///     拼接枚举值：
    ///         <c>new List<DomainType> { DomainType.GuanHao, DomainType.YaoJiKe }.Montage(p => ((int)p).ToString(), ","); // 返回："1,2"</c>
    ///     拼接枚举名：
    ///         <c>new List<DomainType> { DomainType.GuanHao, DomainType.YaoJiKe }.Montage(p => p.ToString(), ","); // 返回："GuanHao,YaoJiKe"</c>
    /// </example>
    /// <typeparam name="T"></typeparam>
    /// <param name="source"></param>
    /// <param name="toString">将列表元素转换为字符串的委托</param>
    /// <param name="splitter">分隔符（可为空）</param>
    /// <returns></returns>
    public static string Montage<T>(this IEnumerable<T> source, Func<T, string> toString, string splitter)
    {
        StringBuilder result = new StringBuilder();
        splitter = splitter ?? string.Empty;
        foreach (T item in source)
        {
            result.Append(toString(item));
            result.Append(splitter);
        }
        string resultStr = result.ToString();
        if (resultStr.EndsWith(splitter))
            resultStr = resultStr.Remove(resultStr.Length - splitter.Length, splitter.Length);
        return resultStr;
    }

    /// <summary>
    /// 从泛型IEnumerable创建一个泛型List，每个元素由converter进行类型转换。
    /// </summary>
    /// <example>
    ///     将枚举List转换为Int32 List：
    ///         <c>new DomainType[] { DomainType.GuanHao, DomainType.YaoJiKe }.ToList(p => (int)p); // 返回：List<int></c>
    /// </example>
    /// <typeparam name="TSource"></typeparam>
    /// <typeparam name="TResult"></typeparam>
    /// <param name="source"></param>
    /// <param name="converter"></param>
    /// <returns></returns>
    public static List<TResult> ToList<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> converter)
    {
        List<TResult> result = new List<TResult>();
        foreach (TSource item in source)
        {
            result.Add(converter(item));
        }
        return result;
    }
}

注意：当最大可移元素是整个数组里最大的那个元素时（本例中是5），可以省略“把所有比 max 大的元素的移动方向反转”那一步，而且只要5是可移的它就一定是最大可移元素，所以可以一直移动5直到不能移动再调用FindMaxMovableItem() 。上面的源码为了简单起见没有做这些工作。

邻位对换法的原理

　　邻位对换法的规则乍一看既简单又奇妙，其实它与本文开篇所提到的递归生成全排列的算法本质上是相同的。在5从最右侧移动到最左侧之后，一定要先使得子数组[1,2,3,4]变成下一个排列[1,2,4,3]，再让5从最左侧移动到最右侧。对于子数组[1,2,3,4]来说，同样是先把4从子数组[1,2,3]的最右侧移动的最左侧，然后让子数组[1,2,3]变成下一个排列[1,3,2]，再让4从它的最左侧移动到最右侧……只不过如果没有递归时的堆栈来保存每一层进行到哪里了，怎么知道每一步应该移动5还是4抑或是3呢？这里必须要先观察得到2个重要的规律，
　　1）只有元素从子数组的一侧移动到另一侧之后才需要把子数组变换成下一个排列。例如只有当4从子数组[1,2,3]的最右侧移动的最左侧之后，才需要让子数组[1,2,3]变成下一个排列[1,3,2]。
　　2）元素一定比子数组中的任何一个元素都大。例如5比子数组[1,2,3,4]的每一个元素都大；4比子数组[1,2,3]的每一个元素都大。
接着我们列出需要知道的3个信息，
　　1）每个元素下一步的移动方向。
　　2）每个元素是否已经移动到了子数组的最左侧或最右侧。
　　3）每一步应该移动哪个元素。
根据上面的2个规律，我们只要为每一个元素增加一个移动方向属性就可以知道这3个信息。首先，当一个元素的移动方向上的邻位比它大或者没有元素时，说明此元素已经到了边界，它暂时不可移，“递归”要下降一层。如果下一层的最大元素也到了边界，就再下降一层。当把子数组变换成新的排列时，再从最上层开始移动元素。“移动方向”属性既保存了移动方向信息，同时也可用于判断元素是否已经移动到了边界。

思考题 请比较邻位对换法里的“递归”与真正的递归方法的区别，然后看看能否写出一个不一样的《盗梦空间》出来。