学步园

一、输出全排列
1、全排列是将一个集合按一定顺序进行排列，如果这个集合有n个元素，那么全排列数为n!个。
2、举例来说，有字符串数组{"x","y","z"},那么该数组对应的全排列就是xyz，xzy，yxz，yzx，zxy，zyx。有人会问，如果集合是{"x","x","z"},那么该数组对应输出的全排列难道是xxz，xzx，xxz，xzx，zxx，zxx吗？按照全排列的定义，是的，我们不关心输出有重复的情况。
3、全排列生成的通项公式
现在我们依照第2步分析归纳全排列的通项公式。为了说明的需要，这一次都从集合的最后一个元素逆向推导，分析如下：
数组有1个元素： {"x"}    对应全排列 x；
数组有2个元素： {"y"."x"}   对应全排列 xy，yx，就是以x开头的y的全排列的组合和以y开头的x的全排列的组合
数组有3个元素： {"z","y","x"}   对应全排列  xyz，xzy，yxz，yzx，zxy，zyx
就是以x开头的y、z的全排列的组合，以y开头的x、z的全排列的组合，以z开头的x、y的全排列的组合
......
依次类推，从而可以推断，设一个数组集合arr = {ele0, ele1, ele2, ... ,ele（n-1）}(n个元素，0，1，2，...n-1为下标), 全排列表示为xyz(arr)，数组关系：dstArri = arr - {ele[i]}，
即原数组arr去掉一个元素，剩下长度n-1的数组dstArri.
因此xyz(arr) = arr[0]xyz(dstArr0), arr[1]xyz(dstArr1), ... ,arr[i]xyz(dstArri), ...。当i=0时xyz(arr) = ele0。
那么如何实现呢？分析一下arr[i]xyz(dstArri)，你可以发现它的规律，就是：将整组中的所有的元素分别与第一个元素交换，这样就总是在处理后n-1个元素的全排列。没错，就是利用递归实现。
4、实现代码
a、c#实现输出集合的全排列

using System;
using System.Collections;
using System.Collections.Generic;

namespace MyCsStudy
{
    class Program
    {
        /// <summary>
        /// 数据元素交换
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="x"></param>
        /// <param name="y"></param>
        static void Swap<T>(ref T x, ref T y)
        {
            T tmp = x;
            x = y;
            y = tmp;
        }

        /// <summary>
        /// 获取数组元素的全排列
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr">需要交换的数组</param>
        /// <param name="k">数组元素开始位置</param>
        /// <param name="m">数组元素个数</param>
        void GetPerm<T>(T[] arr, int arrStart, int arrEnd)
        {
            int i = 0;
            if (arrStart == arrEnd) //全排列的一种情况已经生成
            {
                for (i = 0; i < arrEnd; i++)
                {
                    Console.Write(arr[i]);
                }
                Console.WriteLine("\r");
            }
            else
            {
                for (i = arrStart; i < arrEnd; i++)
                {
                    Swap<T>(ref  arr[arrStart], ref  arr[i]); //交换元素
                    GetPerm<T>(arr, arrStart + 1, arrEnd); //递归调用起始元素后一元素数组生成的全排列
                    Swap<T>(ref  arr[arrStart], ref  arr[i]); //再次交换元素，数组恢复
                }
            }
        }

        static void Main(string[] args)
        {
            Program program = new Program();
            string[] strArr = new string[] { "x", "y","z","a","b","c"};
            program.GetPerm<string>(strArr, 0, strArr.Length); //输出字符串数组全排列

            int[] numArr = new int[6];
            for (int i = 0; i < 6; i++)
            {
                numArr[i] = i;
            }
            program.GetPerm<int>(numArr, 0, numArr.Length);//输出整数数组全排列

            Console.ReadLine();
        }
    }
}

b、javascript实现输出集合的全排列

// JScript 文件
function swap(oArr, oNumEleX, oNumEleY)
{
  var tmp = oArr[oNumEleX];
  oArr[oNumEleX] = oArr[oNumEleY];
  oArr[oNumEleY] = tmp;
}
function getPerm(oArr, arrStart, arrEnd)
{
  var i = 0;
  if (arrStart == arrEnd) 
  {
    for (i = 0; i < arrEnd; i++)
    {
      document.write(oArr[i]);
    }
    document.writeln("<br/>");
  }
  else
  {
    for (i = arrStart; i < arrEnd; i++)
    {
      swap( oArr,arrStart, i);
      getPerm(oArr, arrStart + 1, arrEnd);
      swap( oArr,arrStart, i);
    }
  }
}
function funcTest()
{
  var strArr=new Array("x", "y","z","a","b","c");
  getPerm(strArr,0,strArr.length);
  var numArr=new Array();
  for(var i=0;i<6;i++)
  {
    numArr.push(i);
  }
  getPerm(numArr,0,numArr.length);
}

ps：我们都知道程序中利用递归不当，可能会导致缓冲区溢出。期待高手非递归版本的全排列算法。
二、c#实现数组某段区间元素的交换(o(1)复杂度)
前言：这个纯粹是从老赵那里拿来的，也在我做过的一道笔试题里变相的出现了一下（原题是字符串反转）。这里再贴一次，加深印象。
问题：有一个数组arr，将arr数组元素从start下标到end下标之间的元素反序一下。
举例来说，一个数组初始值是[1, 2, 3, 4, 5, 6,7,8,9,10]，start为1，end为5，那么当调用了Reverse之后，
arr数组中的元素便依次成为[1, 6, 5, 4, 3, 2,7,8,9,10]，其中从arr[1]到arr[5]之间（含arr[5]）的元素被反序了。
下面是c#实现代码：

using System;
using System.Collections;
using System.Collections.Generic;

namespace MyCsStudy
{
    class Program
    {
        /// <summary>
        /// 元素交换
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="x"></param>
        /// <param name="y"></param>
        static void Swap<T>(T[] arr, int start, int end)
        {
            T tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
        }

        /// <summary>
        /// 数组某一区间元素交换
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="start"></param>
        /// <param name="end"></param>
        static void Reverse<T>(T[] arr, int start, int end)
        {
            if (arr == null)
            {
                throw new ArgumentNullException("arr", "数组集合不能为空");
            }

            if (start < 0)
            {
                throw new ArgumentOutOfRangeException("start", "start不能小于0");
            }

            if (end < start)
            {
                throw new ArgumentOutOfRangeException("end不能小于start", (Exception)null);
            }

            if (end >= arr.Length)
            {
                throw new ArgumentOutOfRangeException("end", "end超过arr最大下标");
            }

            while (end > start)
            {
                Swap<T>(arr, start,  end);//数组元素交换

                start++;
                end--;
            }
        }

        static void Main(string[] args)
        {
            int[] intArr = new int[10] ;
            for (int i = 0; i < 10; i++)
            {
                intArr[i] = i + 1;
            }
            for (int i = 0; i < intArr.Length; i++)
            {
                Console.WriteLine(intArr[i]);
            }
            Console.WriteLine("Reverse result:");
            Reverse<int>(intArr, 1, 5);
            for (int i = 0; i < intArr.Length; i++)
            {
                Console.WriteLine(intArr[i]);
            }
            Console.ReadLine();
        }
    }
}

ps：关于数据元素交换肯定不止这一种方法，不过从算法复杂度角度考虑，这一种是很值得提倡的。
三、NC的计算斐波那契数列的第N位
这个NC问题是昨天看到博客园里一位园友的最近遇到的两个面试题兼卖身广告又想起来的。想当初刚毕业那会，被这个面试问题qj很多次，这里贴出递归和迭代两种算法。高手不值一哂，新手也不要当回事，真正的NC问题，哈哈。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpStudy
{
    class Program
    {
        static void Main()
        {
            long num = IterateCalculateFib(40);
            Console.WriteLine(num);

            num = RecurrentCalculateFib(40); //递归  稍微等几秒，看弹出结果，明显慢啊
            Console.WriteLine(num);

            Console.ReadKey();
        }

        /// <summary>
        /// 递归
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long RecurrentCalculateFib(long n)
        {
            if (n < 2)
            {
                return n;
            }
            else
            {
                return RecurrentCalculateFib(n - 1) + RecurrentCalculateFib(n - 2);
            }
        }

        /// <summary>
        /// 迭代
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long IterateCalculateFib(long n)
        {
            long result = 0;
            long x = 0, y = 1, z = 0;
            if (n < 2)
            {
                result = 1;
            }
            else
            {
                for (int i = 2; i <= n; i++)
                {
                    z = x + y; //迭代,将递归里的子运算转换为中间量
                    x = y;
                    y = z;
                }
                result = z;
            }
            return result;
        }

    }
}