白话算法(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 大的元素的移动方向反转
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的完整代码如下。view sourceprint?// 带有方向的元素
[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)
&nb
补充：移动开发 , 其他 ,
