C#实现排列组合算法
数学中排列组合,排列P（N，R）
其实排列实现了，组合也就实现了组合C(N,R)就是P(N,R)/P(R,R) ，比较简单的是递归算法，但考虑到递归的性能，下面采用了2种非递归的方法，代码如下
view sourceprint?01 using System;
02 using System.Collections.Generic;
03 namespace Test
04 {
05 class Program
06 {
07 static void Main(string[] args)
08 {
09 Console.WriteLine(P1(6, 3));
10 Console.WriteLine(P2(6, 3));
11 Console.WriteLine(C(6, 2));
12 }
13
14 /// <summary>
15 /// 排列循环方法
16 /// </summary>
17 /// <param name="N"></param>
18 /// <param name="R"></param>
19 /// <returns></returns>
20 static long P1(int N, int R)
21 {
22 if (R > N || R <= 0 || N <= 0 ) throw new ArgumentException("params invalid!");
23 long t = 1;
24 int i = N;
25
26 while (i!=N-R)
27 {
28 try
29 {
30 checked
31 {
32 t *= i;
33 }
34 }
35 catch
36 {
37 throw new OverflowException("overflow happens!");
38 }
39 --i;
40 }
41 return t;
42 }
43
44 /// <summary>
45 /// 排列堆栈方法
46 /// </summary>
47 /// <param name="N"></param>
48 /// <param name="R"></param>
49 /// <returns></returns>
50 static long P2(int N, int R)
51 {
52 if (R > N || R <= 0 || N <= 0 ) throw new ArgumentException("arguments invalid!");
53 Stack<int> s = new Stack<int>();
54 long iRlt = 1;
55 int t;
56 s.Push(N);
57 while ((t = s.Peek()) != N - R)
58 {
59 try
60 {
61 checked
62 {
63 iRlt *= t;
64 }
65 }
66 catch
67 {
68 throw new OverflowException("overflow happens!");
69 }
70 s.Pop();
71 s.Push(t - 1);
72 }
73 return iRlt;
74 }
75
76 /// <summary>
77 /// 组合
78 /// </summary>
79 /// <param name="N"></param>
80 /// <param name="R"></param>
81 /// <returns></returns>
82 static long C(int N, int R)
83 {
84 return P1(N, R) / P1(R, R);
85 }
86 }
87
88 }
