combinatorics.cs

求 排列组合,用.net实现,能求出所有的排列组合情况

using System;
using System.Collections;
using System.Data;

/// <summary>
/// Summary description for Class1
/// </summary>
public class Combinatorics
{
    public Combinatorics()
	{
        
		//
		// TODO: Add constructor logic here
		//
	}

    public static DataTable TwoDemisionIntArrayToDataTable(int[,] source)
    {
        DataTable dt = new DataTable();
        DataRow dr;
        int i, j;

        int b1 = source.GetUpperBound(0), b2 = source.GetUpperBound(1);                //获取二维表的各维长度                          

        for (i = 0; i <= b1; i++)                                                         //以第二维长度创建数据表的各字段 
            dt.Columns.Add(i.ToString(), System.Type.GetType("System.Int32"));

        for (i = 0; i <= b2; i++)                                                         //对各返回排列循环 
        {
            dr = dt.NewRow();                                                              //准备插入新行 
            for (j = 0; j <= b1; j++)                                                    //在新行中逐个填入返回排列的各元素次序                 
                dr[j.ToString()] = source[j, i];                                      //用序数指针获取原元素的值 
            dt.Rows.Add(dr);                                                               //插入新行 
        }

        return dt;
    }

    /// <summary> 
    /// 连乘积函数          
    /// </summary> 
    public static int Product(int start, int finish)
    {
        int factorial = 1;
        for (int i = start; i <= finish; i++)
            factorial *= i;
        return factorial;
    }

    /// <summary> 
    /// 阶乘函数        
    /// </summary> 
    public static int Factorial(int n)
    {
        return Product(2, n);
    }

    /// <summary> 
    /// 排列数函数          
    /// </summary> 
    public static int ArrangeCount(int m, int n)
    {
        return Product(n - m + 1, n);
    }

    /// <summary> 
    /// 生成排列表函数      
    /// </summary> 
    public static int[,] Arrange(int m, int n)
    {
        int A = ArrangeCount(m, n);               //求得排列数，安排返回数组的第一维 
        int[,] arrange = new int[m, A];           //定义返回数组 
        ArrayList e = new ArrayList();            //设置元素表 
        for (int i = 0; i < n; i++)
            e.Add(i + 1);
        Arrange(ref arrange, e, m, 0, 0);
        return arrange;
    }

    /// <summary> 
    /// 组合数函数          
    /// </summary> 
    public static int CombinationCount(int m, int n)
    {
        int a = Product(n - m + 1, n), b = Product(2, m);       //a=n-m+1 * ... * n ; b = m! 
        return (int)a / b;                                            //c=a/b                               
    }

    /// <summary> 
    /// 生成组合表函数      
    /// </summary> 
    public static int[,] Combination(int m, int n)
    {
        int A = CombinationCount(m, n);                //求得排列数，安排返回数组的第一维 
        int[,] combination = new int[m, A];            //定义返回数组 
        ArrayList e = new ArrayList();                 //设置元素表 
        for (int i = 0; i < n; i++)
            e.Add(i + 1);
        Combination(ref combination, e, m, 0, 0);
        return combination;
    }

    /// <summary> 
    /// 排列函数 
    /// </summary> 
    /// <param name="reslut">返回值数组</param> 
    /// <param name="elements">可供选择的元素数组</param> 
    ///  <param name="m">目标选定元素个数</param>            
    /// <param name="x">当前返回值数组的列坐标</param> 
    /// <param name="y">当前返回值数组的行坐标</param> 
    private static void Arrange(ref int[,] reslut, ArrayList elements, int m, int x, int y)
    {
        int sub = ArrangeCount(m - 1, elements.Count - 1);                    //求取当前子排列的个数 
        for (int i = 0; i < elements.Count; i++, y += sub)                    //每个元素均循环一次,每次循环后移动行指针 
        {
            int val = RemoveAndWrite(elements, i, ref reslut, x, y, sub);
            if (m > 1)                                                                 //递归条件为子排列数大于1 
                Arrange(ref reslut, elements, m - 1, x + 1, y);
            elements.Insert(i, val);                                              //恢复刚才删除的元素                   
        }
    }

    /// <summary> 
    /// 组合函数 
    /// </summary> 
    /// <param name="reslut">返回值数组</param> 
    /// <param name="elements">可供选择的元素数组</param> 
    ///  <param name="m">目标选定元素个数</param>            
    /// <param name="x">当前返回值数组的列坐标</param> 
    /// <param name="y">当前返回值数组的行坐标</param> 
    private static void Combination(ref int[,] reslut, ArrayList elements, int m, int x, int y)
    {
        ArrayList tmpElements = new ArrayList();                              //所有本循环使用的元素都将暂时存放在这个数组 
        int elementsCount = elements.Count;                                        //先记录可选元素个数 
        int sub;
        for (int i = elementsCount - 1; i >= m - 1; i--, y += sub)            //从elementsCount-1(即n-1)到m-1的循环,每次循环后移动行指针 
        {
            sub = CombinationCount(m - 1, i);                                   //求取当前子组合的个数 
            int val = RemoveAndWrite(elements, 0, ref reslut, x, y, sub);
            tmpElements.Add(val);                                                 //把这个可选元素存放到临时数组,循环结束后一并恢复到elements数组中                  
            if (sub > 1 || (elements.Count + 1 == m && elements.Count > 0))  //递归条件为 子组合数大于1 或 可选元素个数+1等于当前目标选择元素个数且可选元素个数大于1 
                Combination(ref reslut, elements, m - 1, x + 1, y);
        }
        elements.InsertRange(0, tmpElements);                                 //一次性把上述循环删除的可选元素恢复到可选元素数组中            
    }

    /// <summary> 
    /// 返回由Index指定的可选元素值,并在数组中删除之,再从y行开始在x列中连续写入subComb个值 
    /// </summary> 
    private static int RemoveAndWrite(ArrayList elements, int index, ref int[,] reslut, int x, int y, int count)
    {
        int val = (int)elements[index];
        elements.RemoveAt(index);
        for (int i = 0; i < count; i++)
            reslut[x, y + i] = val;
        return val;
    }         
          



    /*
        static int resultcount = 0;
        public static void quanpailie(char[] list, int start, int end)//递归的产生全排列
        {
            if (start == end)
            {
                for (int i = 0; i <= end; i++)
                {

                    Console.Write("{0}", list[i]);

                }
                Console.WriteLine();
                resultcount++;
            }
            else
            {
                for (int i = start; i < end; i++)
                {
                    swap(ref list[start], ref list[i]);//交换位置
                    quanpailie(list, start + 1, end);
                    swap(ref list[start], ref list[i]);//交换位置


                }



            }
        }
        public static void swap(ref char a, ref char b)
        {
            char temp;
            temp = a;
            a = b;
            b = temp;

        }
        */


}