递归枚举排列、组合的C#源码

大约是2001年时候用VS7 beta写的一点东西了，现在回看起来不是一般的幼稚。。。好处是还能运行：）,看到CSDN上有朋友要C# 的代码，我也不揣简陋，献丑了。(转换成VS03的工程了）

Combinatorics.cs代码清单

using System;

using System.Collections;

using System.Data;

/// <summary>

/// 组合数学函数集

/// </summary>

public class Combinatorics

{

#region 公共函数

/// <summary>

/// 把二维整形数组转换为数据表

/// </summary>

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;

}

#endregion

#region 内部核心

/// <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;

}

#endregion

}

测试窗体frmTest.cs代码清单:

using System;

using System.Drawing;

using System.Collections;

using System.ComponentModel;

using System.Windows.Forms;

using System.Data;

namespace CombinatoricsLib

{

/// <summary>

/// Form1 的摘要说明。

/// </summary>

public class frmTest : System.Windows.Forms.Form

{

private System.Windows.Forms.DataGrid gridShow;

private System.Windows.Forms.NumericUpDown numM;

private System.Windows.Forms.Button btnGo;

private System.Windows.Forms.DomainUpDown domainFunction;

private System.Windows.Forms.StatusBar statusBar1;

private System.Windows.Forms.StatusBarPanel panelErrMsg;

private System.Windows.Forms.NumericUpDown numN;

/// <summary>

/// 必需的设计器变量。

/// </summary>

private System.ComponentModel.Container components = null;

public frmTest()

{

// Windows 窗体设计器支持所必需的

InitializeComponent();

// TODO: 在 InitializeComponent 调用后添加任何构造函数代码

}

/// <summary>

/// 清理所有正在使用的资源。

/// </summary>

protected override void Dispose( bool disposing )

{

if( disposing )

{

if (components != null)

{

components.Dispose();

}

base.Dispose( disposing );

}

#region Windows 窗体设计器生成的代码

/// <summary>

/// 设计器支持所需的方法 - 不要使用代码编辑器修改

/// 此方法的内容。

/// </summary>

private void InitializeComponent()

{

this.gridShow = new System.Windows.Forms.DataGrid();

this.domainFunction = new System.Windows.Forms.DomainUpDown();

this.numM = new System.Windows.Forms.NumericUpDown();

this.numN = new System.Windows.Forms.NumericUpDown();

this.btnGo = new System.Windows.Forms.Button();

this.statusBar1 = new System.Windows.Forms.StatusBar();

this.panelErrMsg = new System.Windows.Forms.StatusBarPanel();

((System.ComponentModel.ISupportInitialize)(this.gridShow)).BeginInit();

((System.ComponentModel.ISupportInitialize)(this.numM)).BeginInit();

((System.ComponentModel.ISupportInitialize)(this.numN)).BeginInit();

((System.ComponentModel.ISupportInitialize)(this.panelErrMsg)).BeginInit();

this.SuspendLayout();

// gridShow

this.gridShow.AlternatingBackColor = System.Drawing.Color.Lavender;

this.gridShow.BackColor = System.Drawing.Color.WhiteSmoke;

this.gridShow.BackgroundColor = System.Drawing.Color.LightGray;

this.gridShow.BorderStyle = System.Windows.Forms.BorderStyle.None;

this.gridShow.CaptionBackColor = System.Drawing.Color.LightSteelBlue;

this.gridShow.CaptionForeColor = System.Drawing.Color.MidnightBlue;

this.gridShow.DataMember = "";

this.gridShow.FlatMode = true;

this.gridShow.Font = new System.Drawing.Font("Tahoma", 8F);

this.gridShow.ForeColor = System.Drawing.Color.MidnightBlue;

this.gridShow.GridLineColor = System.Drawing.Color.Gainsboro;

this.gridShow.GridLineStyle = System.Windows.Forms.DataGridLineStyle.None;

this.gridShow.HeaderBackColor = System.Drawing.Color.MidnightBlue;

this.gridShow.HeaderFont = new System.Drawing.Font("Tahoma", 8F, System.Drawing.FontStyle.Bold);

this.gridShow.HeaderForeColor = System.Drawing.Color.WhiteSmoke;

this.gridShow.LinkColor = System.Drawing.Color.Teal;

this.gridShow.Location = new System.Drawing.Point(24, 88);

this.gridShow.Name = "gridShow";

this.gridShow.ParentRowsBackColor = System.Drawing.Color.Gainsboro;

this.gridShow.ParentRowsForeColor = System.Drawing.Color.MidnightBlue;

this.gridShow.ReadOnly = true;

this.gridShow.SelectionBackColor = System.Drawing.Color.CadetBlue;

this.gridShow.SelectionForeColor = System.Drawing.Color.WhiteSmoke;

this.gridShow.Size = new System.Drawing.Size(648, 344);

this.gridShow.TabIndex = 0;

// domainFunction

this.domainFunction.BackColor = System.Drawing.SystemColors.Info;

this.domainFunction.Font = new System.Drawing.Font("宋体", 36F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((System.Byte)(134)));

this.domainFunction.ForeColor = System.Drawing.Color.Teal;

this.domainFunction.Items.Add("C");

this.domainFunction.Items.Add("A");

this.domainFunction.Location = new System.Drawing.Point(24, 8);

this.domainFunction.Name = "domainFunction";

this.domainFunction.ReadOnly = true;

this.domainFunction.Size = new System.Drawing.Size(48, 62);

this.domainFunction.TabIndex = 1;

this.domainFunction.Text = "C";

// numM

this.numM.BackColor = System.Drawing.Color.PeachPuff;

this.numM.Font = new System.Drawing.Font("宋体", 12F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((System.Byte)(134)));

this.numM.ForeColor = System.Drawing.Color.Teal;

this.numM.Location = new System.Drawing.Point(80, 8);

this.numM.Maximum = new System.Decimal(new int[] {

20,

0});

this.numM.Minimum = new System.Decimal(new int[] {

0});

this.numM.Name = "numM";

this.numM.Size = new System.Drawing.Size(56, 26);

this.numM.TabIndex = 4;

this.numM.Value = new System.Decimal(new int[] {

0});

// numN

this.numN.BackColor = System.Drawing.Color.Bisque;

this.numN.Font = new System.Drawing.Font("宋体", 12F);

this.numN.ForeColor = System.Drawing.Color.Teal;

this.numN.Location = new System.Drawing.Point(80, 40);

this.numN.Maximum = new System.Decimal(new int[] {

25,

0});

this.numN.Minimum = new System.Decimal(new int[] {

0});

this.numN.Name = "numN";

this.numN.Size = new System.Drawing.Size(56, 26);

this.numN.TabIndex = 5;

this.numN.Value = new System.Decimal(new int[] {

0});

// btnGo

this.btnGo.BackColor = System.Drawing.Color.PaleTurquoise;

this.btnGo.Location = new System.Drawing.Point(184, 24);

this.btnGo.Name = "btnGo";

this.btnGo.Size = new System.Drawing.Size(88, 32);

this.btnGo.TabIndex = 6;

this.btnGo.Text = "Go!";

this.btnGo.Click += new System.EventHandler(this.btnGo_Click);

// statusBar1

this.statusBar1.Location = new System.Drawing.Point(0, 453);

this.statusBar1.Name = "statusBar1";

this.statusBar1.Panels.AddRange(new System.Windows.Forms.StatusBarPanel[] {

this.panelErrMsg});

this.statusBar1.ShowPanels = true;

this.statusBar1.Size = new System.Drawing.Size(704, 32);

this.statusBar1.TabIndex = 7;

this.statusBar1.Text = "statusBar1";

// panelErrMsg

this.panelErrMsg.AutoSize = System.Windows.Forms.StatusBarPanelAutoSize.Contents;

this.panelErrMsg.Text = "Idle";

this.panelErrMsg.Width = 39;

// frmTest

this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);

this.ClientSize = new System.Drawing.Size(704, 485);

this.Controls.Add(this.statusBar1);

this.Controls.Add(this.btnGo);

this.Controls.Add(this.numN);

this.Controls.Add(this.numM);

this.Controls.Add(this.domainFunction);

this.Controls.Add(this.gridShow);

this.MaximizeBox = false;

this.Name = "frmTest";

this.StartPosition = System.Windows.Forms.FormStartPosition.CenterScreen;

this.Text = "frmTest";

((System.ComponentModel.ISupportInitialize)(this.gridShow)).EndInit();

((System.ComponentModel.ISupportInitialize)(this.numM)).EndInit();

((System.ComponentModel.ISupportInitialize)(this.numN)).EndInit();

((System.ComponentModel.ISupportInitialize)(this.panelErrMsg)).EndInit();

this.ResumeLayout(false);

}

#endregion

/// <summary>

/// 应用程序的主入口点。

/// </summary>

[STAThread]

static void Main()

{

Application.Run(new frmTest());

}

private void btnGo_Click(object sender, System.EventArgs e)

{

int[, ]reslut;

int m = (int)numM.Value, n = (int)numN.Value;

if (m <= n)

{

panelErrMsg.Text = "Running...";

if (domainFunction.Text == "A")

reslut = Combinatorics.Arrange(m, n);

else

reslut = Combinatorics.Combination(m, n);

panelErrMsg.Text = "Showing...";

gridShow.DataSource = Combinatorics.TwoDemisionIntArrayToDataTable(reslut);

panelErrMsg.Text = "Idle";

}

else

panelErrMsg.Text = "Input number is invalid";

}

运行效果如图：

感觉没什么好废话的，用DataTable输出就是为了方便绑定实体值（比如做攻击字典）的枚举。各路高人见笑了。