递归和非递归算法实现的全排列类库

Posted on by 

/* ----------------------------------------------------------
 * 文件名称：FullPermutation.cs
 * 
 * 作者：秦建辉
 * 
 * QQ：36748897
 * 
 * 版本历史：
 *      V1.0	2011年06月22日
 *              递归和非递归算法实现的全排列类库
 *              
 * 参考资料：
 *      http://plutoblog.iteye.com/blog/976216
 *      http://tieba.baidu.com/f?kz=12248706
 * ------------------------------------------------------------ */
using System;
using System.Collections.Generic;

namespace Splash
{
    /// <summary>
    /// 递归和非递归实现按顺序输出的全排列类库
    /// </summary>
    public static class FullPermutation
    {
        /// <summary>
        /// 递归实现的按顺序输出的全排列数组列表
        /// </summary>
        /// <param name="index">起始索引号</param>
        /// <param name="length">元素个数</param>
        /// <returns>全排列数组列表</returns>
        public static List<Int32[]> Seed(Int32 index, Int32 length)
        {
            if (length <= 0) return null;

            Int32[] used = new Int32[length];
            Int32[] result = new Int32[length];
            List<Int32[]> list = new List<Int32[]>();

            Array.Clear(used, 0, length);   // 初始化
            Proc(0, index, length, list, used, result);

            return list;
        }

        // 递归实现
        private static void Proc(Int32 step, Int32 index, Int32 length, List<Int32[]> list, Int32[] used, Int32[] result)
        {
            if (step == length)
            {
                list.Add((Int32[])result.Clone());  // 注意：克隆数组
            }
            else
            {
                for (Int32 i = 0; i < length; i++)
                {
                    if (used[i] == 0)   // 未处理
                    {
                        used[i] = 1;
                        result[step] = index + i;
                        Proc(step + 1, index, length, list, used, result);
                        used[i] = 0;
                    }
                }
            }
        }

        /// <summary>
        /// 非递归实现的按顺序输出的全排列迭代器
        /// </summary>
        /// <param name="index">起始索引号</param>
        /// <param name="length">元素个数</param>
        /// <returns>全排列迭代器</returns>
        /// <remarks>
        /// 基本思想：
        ///     1. 找到所有排列中最小的一个排列P
        ///     2. 找到刚刚好比P大比其它都小的排列Q
        ///     3. 循环执行第二步,直到找到一个最大的排列,算法结束
        /// </remarks>
        public static System.Collections.IEnumerable Cell(Int32 index, Int32 length)
        {
            if (length <= 0)
            {   // 迭代结束
                yield break;
            }
            else if (length == 1)
            {   // 只有一个元素
                yield return new Int32[] { index };
            }
            else
            {   // 生成一个最小排列
                Int32[] A = new Int32[length];
                for (Int32 i = 0; i < length; i++)
                    A[i] = index + i;

                while (true)
                {
                    yield return A;

                    Int32 i, j;

                    // 从后向前找出不符合从大到小的元素A[i]
                    for (i = length - 2; i >= 0; i--)
                    {
                        if (A[i] < A[i + 1])
                            break;
                        else if (i == 0)
                            yield break;    // 所有元素都满足从大到小，迭代结束
                    }

                    // 从后向前找出比其大的元素A[j]
                    for (j = length - 1; j > i; j--)
                    {
                        if (A[j] > A[i]) break;
                    }

                    // 交换A[i]和A[j]
                    A[i] ^= A[j];
                    A[j] ^= A[i];
                    A[i] ^= A[j];

                    // 反转后面的元素，使A[i]后面的元素变成最小排列
                    Array.Reverse(A, i + 1, length - i - 1);
                }
            }
        }
    }
}

调用示例：

using System;
using System.Collections.Generic;

namespace Splash
{
    class Program
    {
        static void Main(string[] args)
        {
            String s = "abcde";

            // 测试全排列列表
            Console.WriteLine("测试全排列列表");
            List<Int32[]> list = FullPermutation.Seed(0, 3);
            if (list != null)
            {
                foreach (Int32[] item in list)
                {
                    for (Int32 i = 0; i < item.Length; i++)
                    {
                        if (i != 0) Console.Write(" ");
                        Console.Write(s[item[i]]);
                    }
                    Console.WriteLine();
                }
            }

            // 测试迭代器
            Console.WriteLine();
            Console.WriteLine("测试迭代器");
            foreach (Int32[] item in FullPermutation.Cell(0, 3))
            {
                for (Int32 i = 0; i < item.Length; i++)
                {
                    if (i != 0) Console.Write(" ");
                    Console.Write(s[item[i]]);
                }
                Console.WriteLine();
            }
        }
    }
}

Comments are closed.