求全排列的小程序

Question

用非递归回溯的思想写段小程序，求[0, n-1]间索引的全排列，还未优化。    /// <summary>
    /// 组合数学辅助类 。
    /// </summary>
    public static class CombinatoricsHelper
    {
        #region public static methods
        /// <summary>
        /// 生成[n, count)索引全排列，并操作 。
        /// </summary>
        /// <param name="visitor">访问函数 。</param>
        /// <param name="count">数目，索引范围在[0, count - 1]间 。</param>
        /// <exception cref="ArgumentNullException">如果visitor为null，抛出ArgumentNullException 。</exception>
        /// <exception cref="ArgumentOutOfRangeException">如果count非法，抛出ArgumentOutOfRangeException 。</exception>
        public static void VisitPermutationIndice(Action<IList<int>> visitor, int count)
        {
            VisitPremutationIndiceBackTrackingImpl(visitor, count);
        }
        #endregion        #region private static methods
        /// <summary>
        /// 生成[n, count)索引全排列，并操作，使用回溯算法实现 。
        /// </summary>
        /// <param name="visitor">访问函数 。</param>
        /// <param name="count">数目，索引范围在[0, count - 1]间 。</param>
        /// <exception cref="ArgumentNullException">如果visitor为null，抛出ArgumentNullException 。</exception>
        /// <exception cref="ArgumentOutOfRangeException">如果count非法，抛出ArgumentOutOfRangeException 。</exception>
        private static void VisitPremutationIndiceBackTrackingImpl(Action<IList<int>> visitor, int count)
        {
            if (visitor == null)
            {
                throw new ArgumentNullException("visitor");
            }            if (count <= 0)
            {
                throw new ArgumentOutOfRangeException("count");
            }            const int NonFill = -1; // 未填充索引
            bool isFin = false; // 是否完成排列
            int filledCount = 0; // 当前已填充的数目
            int fillNum = 0; // 要填充的数，临时变量
            bool isPermutation = false; // 是否为排列之一，临时变量
            int[] indice = new int[count];
            for (int i = 0; i < count; i++)
            {
                indice[i] = NonFill;
            }            while (!isFin)
            {
                // 填充数
                fillNum = NonFill;
                for (int i = 0; i < count; i++)
                {
                    int findIndex = (filledCount <= 0) ? -1 : Array.FindIndex<int>(indice, 0, filledCount, num => num == i);
                    if (findIndex < 0)
                    {
                        fillNum = i;
                        break;
                    }
                }                if (fillNum < 0)
                { // 不应该进入此错误路径
                    throw new InvalidOperationException();
                }
                
                indice[filledCount] = fillNum;
                filledCount++;                // 判断是否填充完全
                isPermutation = (filledCount == count) ? true : false;
                if (isPermutation)
                {
                    visitor(indice);
                }                // 如果填充完成，尝试回溯，如果不需要再回溯，则可以退出循环
                if (isPermutation)
                {
                    int lastBackTrackIndex = -1; // 最近的回溯点索引，找最近一条未填充完全的索引
                    for (int i = filledCount - 1; i >= 0; i--)
                    {
                        // [i, filledCount -1]如果为升序排列，则无法作为回溯
                        bool isAscendOrder = true;
                        int prev = indice[i];
                        for (int j = i + 1; j < filledCount; j++)
                        {
                            if (prev < indice[j])
                            {
                                isAscendOrder = false;
                                break;
                            }                            prev = indice[j];
                        }                        if (!isAscendOrder)
                        {
                            lastBackTrackIndex = i;
                            break;
                        }
                    }
                   
                    if (lastBackTrackIndex < 0)
                    { // 如果没有回溯点
                        isFin = true;
                    }
                    else
                    {
                        for (int i = lastBackTrackIndex + 1; i < filledCount; i++)
                        { // 赋初值重新填充
                            indice[i] = NonFill; 
                        }                        fillNum = NonFill;
                        for (int i = indice[lastBackTrackIndex] + 1; i < count; i++)
                        {
                            int findIndex = (filledCount <= 0) ? -1 : Array.FindIndex<int>(indice, 0, filledCount, num => num == i);
                            if (findIndex < 0)
                            {
                                fillNum = i;
                                break;
                            }
                        }                        if (fillNum < 0)
                        { // 不应该进入此错误路径
                            throw new InvalidOperationException();
                        }                        indice[lastBackTrackIndex] = fillNum;
                        filledCount = lastBackTrackIndex + 1;
                    }
                }
            }
        }
        #endregion
    }

Answer 1

非递归全排列。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = Arrange(4);
            foreach (var item in result)
            {
                Console.WriteLine(string.Join(",", item.Select(x => x.ToString()).ToArray()));
            }
        }        static List<List<int>> Arrange(int n)
        {
            var result = Enumerable.Range(0, n).Select(x => new List<int>() { x }).ToList();
            while (result[0].Count < n)
            { 
                result = result.SelectMany(x => Enumerable.Range(0, n).Except(x).Select(y => x.Concat(new List<int>() { y }).ToList())).ToList();
            }
            return result;
        }
    }
}0,1,2,3
0,1,3,2
0,2,1,3
0,2,3,1
0,3,1,2
0,3,2,1
1,0,2,3
1,0,3,2
1,2,0,3
1,2,3,0
1,3,0,2
1,3,2,0
2,0,1,3
2,0,3,1
2,1,0,3
2,1,3,0
2,3,0,1
2,3,1,0
3,0,1,2
3,0,2,1
3,1,0,2
3,1,2,0
3,2,0,1
3,2,1,0
Press any key to continue . . .

Answer 2

递归的版本参考：
http://topic.csdn.net/u/20110625/22/9b9906a7-ca3e-4b31-bc8d-815774d7ce64.html
我的回答。

Answer 3

  /// <summary>
  /// 生成[n, count)索引全排列，并操作，使用回溯算法实现 。
  /// </summary>
  /// <param name="visitor">访问函数 。</param>
  /// <param name="count">数目，索引范围在[0, count - 1]间 。</param>
  /// <exception cref="ArgumentNullException">如果visitor为null，抛出ArgumentNullException 。</exception>
  /// <exception cref="ArgumentOutOfRangeException">如果count非法，抛出ArgumentOutOfRangeException 。</exception>
经常遇到这样的xml 但知道它的作用到底是啥？难道就是纯粹的为了跟踪程序么和注释的作用么？？。

Answer 4

sp1234的意思我不是很清楚，我估计他是说使用yield return语法配合IEnumerable<T>实现延迟加载的枚举类，它的开销是很小的，至少在存储上。

Answer 5

递归是不是就是用的堆栈来计算的啊?我的理解是这样的,大侠指点下...看到sp1234 提到才想到 递归有堆栈的联系..::假如 一个递归算法,需要递归100次... 然后pop.push(100)......pop.push(1)..这样先堆好了 在 pop.drop(1)............ pop.drop(100),这样来计算的....假如drop(1)执行的时间复杂度是N 
那么时间复杂度是多少?100N?....另外迭代应该就是通过指针++ 来存储数据的吧???