瓶水相逢 - 艾小克

Keeping a low profile.

2008-03-18

C# - 產生 Combination - C(n, r) 組合問題

C# - 產生 Combination - C(n, r) 組合問題

Combination

Combination 可以拿來當作包牌程式，挑選號碼集合 n，在進行 C(n, 6) 即可。

程式碼：

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  4. namespace Combination
  5. {
  6. public class Combination
  7. {
  8. private int m_n = 0;
  9. private int m_r = 0;
  10. private int m_totalNum = 0;
  11. private int m_leftNum = 0;
  12. private int [ ] sString;
  13. public int N
  14. {
  15. get { return m_n; }
  16. set { m_n = value; }
  17. }
  18. public int R
  19. {
  20. get { return m_r; }
  21. set
  22. {
  23. if (value < this.N )
  24. {
  25. m_r = value;
  26. }
  27. else
  28. {
  29. m_r = 1;
  30. }
  31. }
  32. }
  33. public int TotalNum
  34. {
  35. get { return m_totalNum; }
  36. set { m_totalNum = value; }
  37. }
  38. public int LeftNum
  39. {
  40. get { return m_leftNum; }
  41. set { m_leftNum = value; }
  42. }
  43. // calcualte n!
  44. public int factorial( int n)
  45. {
  46. int result = 1;
  47. for ( int i = n; i >= 1; i--)
  48. {
  49. result *= i;
  50. }
  51. return result;
  52. }
  53. // Constructor
  54. public Combination( int n, int r)
  55. {
  56. this.N = n;
  57. this.R = r;
  58. this.TotalNum = factorial( this.N )/(factorial( this.N - this.R )*factorial( this.R ) );
  59. this.LeftNum = this.TotalNum;
  60. sString = new int [ this.R ];
  61. reset( ref sString);
  62. }
  63. // Are there more combination?
  64. public bool hasMore( )
  65. {
  66. return ( this.LeftNum == 0 ) ? false : true;
  67. }
  68. // Reset
  69. public void reset( ref int [ ] sString)
  70. {
  71. for ( int i = 0; i < sString.Length; i++)
  72. {
  73. sString[i] = i;
  74. }
  75. }
  76. // Generate next combination
  77. public int [ ] getNext( )
  78. {
  79. int i = this.R - 1;
  80. if ( this.LeftNum == this.TotalNum )
  81. {
  82. this.LeftNum -= 1;
  83. return sString;
  84. }
  85. while (sString[i] == this.N - this.R + i)
  86. {
  87. i--;
  88. }
  89. sString[i] += 1;
  90. for ( int j = i + 1; j < this.R; j++)
  91. {
  92. sString[j] = sString[i] + j - i;
  93. }
  94. this.LeftNum -= 1;
  95. return sString;
  96. }
  97. }
  98. internal class Program
  99. {
  100. private static void Main( string [ ] args)
  101. {
  102. Console.Write ( "Please input set: " );
  103. string [ ] sign = Console.ReadLine ( ).Split ( ' ' );
  104. // Get r value
  105. Console.Write ( "How many numbers do you select: " );
  106. int rValue;
  107. if ( int.TryParse (Console.ReadLine ( ), out rValue) == false )
  108. {
  109. rValue = 1;
  110. }
  111. Combination c = new Combination(sign.Length, rValue);
  112. int [ ] indices;
  113. List<string> output = new List<string>( );
  114. // Generate all combination
  115. while (c.hasMore ( ) )
  116. {
  117. StringBuilder sb = new StringBuilder( );
  118. indices = c.getNext ( );
  119. for ( int i = 0; i < indices.Length; i++)
  120. {
  121. sb.Append (sign[indices[i] ] );
  122. }
  123. output.Add (sb.ToString ( ) );
  124. }
  125. // List all combination
  126. Console.Write ( "Combination: \n" );
  127. output.Sort ( );
  128. foreach ( string s in output)
  129. {
  130. Console.WriteLine (s);
  131. }
  132. Console.WriteLine ( "\npress any key to exit" );
  133. Console.Read ( );
  134. }
  135. }
  136. }