瓶水相逢 - 艾小克

Keeping a low profile.

2008-03-18

C# - 產生 Permutation - P(n) 排列問題

C# - 產生 Permutation - P(n) 排列問題

Permutation



程式碼：

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