基于N层满N叉树的排列算法
原文地址:http://www.netcsharp.cn/showtopic-698.aspx排列是组合数学问题，而很多组合数学问题都可以在图之间进行转换。树是一种特殊的图。在这里我用一种特殊的树结构实现排列算法，这种树就是N层满N叉树（N可以是任意自然数）。图一就是一个三层满三叉树。它刚好有3层，并且除叶结点外每节点有3个儿子。利用这种树的性质我们很容易就能直观的获得一个3排列。
下面就让我们试着一个个将一个3排列得出来。
首先我们先看看一个3排列的最终结果是怎样的，从初中的数学我们也很容易得知：排列的总数=3!=3*2*1=6个。我们将数字0，1，2作为排列的元素，并且特意如图一、图二、图三的样子各自形成一个三层满三叉树。聪明的读者不难发现三棵树的规律。它们的顶点分别是0、1、2，而他们的子节点则是顺序排列的0、1、2。这些子节点又按同样的规律拥有其三个子节点。至此，我们就不难理解什么是所谓的“N层满N叉树”了。
接下来，我们从图一开始数组合。绿色的节点代表选中的。凡是选中的我们用一个布尔数组mSelected标记起来，并用另外一个数组mResult作为输出。mResult的下标是树的层数，用于纪录某一层所选的数字。
int level;
int total = 3;
//已选节点的标记数组
bool[] mSelected = new bool[ total ];
//已选节点的标记数组
int[] mResult = new int[ total ];
（1）选a，因为a等于0，而mSelected[0]等于false，所以设置mSelected[0]为true。由于a是第0层，所以设置mResult[0]为0;
（2）对于b，因为b等于0，而mSelected[0]已经等于true，也就是说0已经在结果数组mResult中了，所以节点b以及其后代可以被忽略掉，就如b上的删除符号所表示的；
（3）然后我们可以考察节点c,c等于1，而mSelected[1]等于false，所以可以mSelected[1]为true，而c在第1层，所以mResult[1]为1;
（4）d,e同b一样都是已经选过的（在mSelected中对应位置为true）所以也被忽略掉;
（5）f等于2，并且mSelected[2]等于false，所以可以mSelected[2]为true，而f在层2，所以mResult[2]设为2。到这里，我们已经到达了树的低层，这意味着一个排列结果已经出来了。正如图一所示为mResult中的0,1,2。
（6）当回溯到g节点，我们需要对mSelected和mResult数组作一些处理，就是将除a节点之外的已选信息更新为false，以便在开始新的搜索前不至于造成错误。为了做到这一点我们可以调用如下循环代码。
//level为回溯到的层，lastSetLevel为上次到达的最底层
for( int i=level;i<=lastSetLevel;i++ ) {
mSelected[mResult] = false;
}
（7）考察g（现在除了mSelected[0]为true外，其他的mSelected元素已经被设置为false），因为g等于2,并且 mSelected[2]等于false，所以设置mSelected[2]为true，g在层1，则设置mResult[1]为2。
（8）考察h，因为mSelected[0]为true，所以可以忽略h；
（9）考察I，因为mSelected[1]为false，所以设置mSelected[1]为true，I在层2，则设置mResult[2]为1。同步骤（5）一样，现在已经到达最大层，可以输出mResult中的结果：1,2,0
用同样的方式完成图二，图三的搜索：我们就总共输出了6组的组合结果。如果你熟悉树算法不难得知这是深度优先的树搜索。在实现中可以利用FIFO堆栈。下面是整个算法的代码，我已经将其封装在一个类PermutationGenerator中，只要给出排列个数total，你便可以用foreach语句列举出所有的组合的整形数组。
下次，我给大家讲同样是基于N层满N叉树的组合算法。
完整的PermutationGenerator类代码
// - - - - - 類型 PermutationGenerator - - - - -
public class PermutationGenerator:IEnumerable<int[]> {
private int total;
public int Total { get { return total; }}
// - - - - - 類成員GetEnumerator - - - - -
public IEnumerator<int[]> GetEnumerator( ) {
//########################
// ############## Stack Info
int stackidx = 0;
int stkSize = total * total / 2;
int[] stack_num = new int[ stkSize ];
int[] stack_level = new int[ stkSize ];
//########################
int totalminus1 = total-1;
int level = 0;
int curpos = -1;
int lastSetLevel = -1;
//
bool[] mSelected = new bool[ total ];
int[] mResult = new int[ total ];
for( int i=totalminus1;i>=0;i-- ){
// Initail Stack , Push
stack_num[ stackidx ] = i;
stack_level[ stackidx ] = level;
stackidx ++;
}
// While Stack not empty
while( stackidx != 0 ) {
// ################
// ########### Pop
stackidx --;
curpos = stack_num[ stackidx ] ;
level = stack_level[ stackidx ];
// ################
for( int i=level;i<=lastSetLevel;i++ ) {
mSelected[mResult] = false;
}
mSelected[curpos] = true;
mResult[level] = curpos;
lastSetLevel = level;
if ( level == totalminus1 ) {
yield return mResult;
}else {
if( level < totalminus1 ) {
for( int i=totalminus1;i>=0;i-- ) {
if( mSelected )continue;
// ################
// ########### Push
stack_num[ stackidx ] = i;
stack_level[ stackidx ] = level+1;
stackidx ++;
}
}
}
}
}
// - - - - - 類成員IEnumerable.GetEnumerator - - - - -
IEnumerator IEnumerable.GetEnumerator( ) {
return GetEnumerator();
}
// - - - - - 類成員PermutationGenerator - - - - -
public PermutationGenerator( int total ) {
if( total < 0 ) throw new Exception( "[TOTAL] can not be less than [ZERO]" );
this.total = total;
}
}
运行的测试程序
public static void Test( ) {
PermutationGenerator pg = new PermutationGenerator( 10 );
foreach( int[] result in pg ) {
StringBuilder sb =new StringBuilder();
for( int i=0;i<result.Length;i++ ) {
sb.Append( result );
sb.Append( "," );
}
Console.WriteLine( sb );
}
}
--------------------编程问答--------------------
补充：.NET技术 , C#
