首页 > 程序开发 > 移动开发 > 其他 >

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

2011-05-23

可以直觉地知道,只要把数组任意相邻的两个元素交换位置,就可以得到一个新的排列。例如把数组 [1,2,3,4,5] 的 5 和 4 交换位置就得到 [1,2,3,5,4],再把 5 和 3 交换位置就得到[1,2,5,3,4]……这样不停地交换就能得到所有的(不重复的)

可以直觉地知道,只要把数组任意相邻的两个元素交换位置,就可以得到一个新的排列。例如把数组 [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

相关文章
最新文章
热点推荐