Wednesday, January 20, 2010

1 2 3 4 5 6 7 8 * * - - / / 9 * * = 2010

ちょっと まえに @hariguchi さんが Knuth せんせいの 誕生日ケーキの 写真を twitter に はっていた

Birthday Cake for Don on Twitpic


なるほど、こういう しきって、あと なんとおり くらい あるんだろう、あとで しらべておこう、って おもったんだけれど、そのことを、せんしゅう にほんに かえった ときに おもいだした。

じかんも あったので、さくっと コードを かいて じっこう。ruby で 100ぎょうくらい。とくに 工夫も せずに ぜんぶ しらべたので えらく じかんが かかった。3じかん じゃく。もし 来年 2011 に なる くみあわせを しらべる ことに なったら、そのときには 半分いかの じかんで うごくように 改良してから じっこう したい。

さて、1 + 2 + 3... という くみあわせを すべて つくって それを 順番に しらべていく のは さすがに むちゃ なので、しきは RPN (Reverse Polish Notation) で ためす。かっこが いらないので シンプル。

けっかは、しきの くみあわせは 93,716,480 とおりで、2010 に 一致 したのは そのうち 186 とおり あった。けっこう ある。

  1. 1 2 3 4 5 - 6 7 * 8 * + 9 * / / *
  2. 1 2 3 4 5 + - 6 7 8 * * * - 9 - +
  3. 1 2 3 4 5 + - 6 * 7 8 * * 9 + - +
  4. 1 2 + 3 4 - 5 - 6 * 7 * 8 * 9 + -
  5. 1 2 + 3 4 5 + - 6 7 8 * * * - 9 -
  6. 1 2 * 3 / 4 5 - 6 7 * 8 * + 9 * *
  7. 1 2 3 4 5 + - 6 * 7 * 8 * - 9 - +
  8. 1 2 * 3 / 4 5 + 6 7 * * 8 * 9 - *
  9. 1 2 3 4 5 6 * 7 8 * + * 9 - * * *
  10. 1 2 3 4 5 - 6 7 8 * * + / 9 / / *
  11. 1 2 3 4 5 + - 6 * 7 8 * * - + 9 -
  12. 1 2 - 3 4 5 6 / 7 8 * + * - - 9 *
  13. 1 2 3 / 4 5 - 6 7 * 8 * + 9 * * *
  14. 1 2 3 / * 4 5 + 6 * 7 * 8 * 9 - *
  15. 1 2 * 3 / 4 5 - 6 7 8 * * + * 9 *
  16. 1 2 + 3 4 5 + - 6 7 * * 8 * 9 + -
  17. 1 2 3 / 4 5 6 7 * 8 * - - * 9 * *
  18. 1 2 3 / 4 5 - 6 7 8 * * + 9 * * *
  19. 1 2 * 3 / 4 5 6 7 * 8 * - - 9 * *
  20. 1 2 3 * * 4 5 6 * 7 8 * + * 9 - *
  21. 1 2 - 3 - 4 5 + 6 / 7 8 * 9 * - *
  22. 1 2 3 4 5 6 + * * 7 - * 8 * + 9 +
  23. 1 2 3 4 5 + 6 7 * * 8 * 9 - / / *
  24. 1 2 3 4 5 + - 6 7 * 8 * * - 9 - +
  25. 1 2 3 4 * + + 5 6 7 8 + 9 * - - *
  26. 1 2 + 3 4 5 + - 6 * 7 8 * * - 9 -
  27. 1 2 3 / 4 5 + 6 7 * * 8 * 9 - * *
  28. 1 2 3 + - 4 5 + 6 / 7 8 9 * * - *
  29. 1 2 3 4 5 6 7 8 * * - - / / 9 * *
  30. 1 2 3 4 5 + 6 7 * 8 * * 9 - / / *
  31. 1 2 * 3 4 5 6 7 8 * * - - 9 * / /
  32. 1 2 * 3 4 5 + 6 * 7 8 * * 9 - / /
  33. 1 2 3 / 4 5 - 6 7 * 8 * + * 9 * *
  34. 1 2 3 4 5 6 7 * 8 + + * + 9 * + +
  35. 1 2 3 4 5 - 6 7 8 * * + / / 9 * *
  36. 1 2 3 4 5 + 6 * 7 8 * * 9 - / / *
  37. 1 2 3 / * 4 5 + 6 7 * * 8 * 9 - *
  38. 1 2 3 / 4 5 - 6 7 8 * * + * 9 * *
  39. 1 2 + 3 4 5 6 7 * + 8 + * + 9 * +
  40. 1 2 + 3 4 - 5 - 6 * 7 8 * * - 9 -
  41. 1 2 3 + - 4 5 6 / 7 8 * + * + 9 *
  42. 1 2 3 4 5 6 7 8 * * - - / 9 / / *
  43. 1 2 + 3 4 - 5 - 6 7 8 * * * - 9 -
  44. 1 2 3 4 - 5 - 6 * 7 8 * * - 9 - +
  45. 1 2 3 4 5 + - 6 7 * * + 8 * 9 - -
  46. 1 2 3 4 * 5 6 + * 7 - 8 * * + 9 +
  47. 1 2 3 4 * 5 6 + * 7 - * 8 * 9 + +
  48. 1 2 3 / * 4 5 - 6 7 8 * * + * 9 *
  49. 1 2 3 4 5 + - 6 * 7 * 8 * 9 + - +
  50. 1 2 3 4 - 5 - 6 7 * * + 8 * - 9 +
  51. 1 2 + 3 4 * + 5 6 7 8 + 9 * - - *
  52. 1 2 + 3 4 5 6 - 7 8 * + * + 9 * +
  53. 1 2 * 3 4 5 6 7 8 * * - - / / 9 *
  54. 1 2 3 / * 4 5 6 7 * 8 * - - 9 * *
  55. 1 2 3 + 4 5 6 / 7 8 * + * - - 9 *
  56. 1 2 + 3 4 5 + * 6 + 7 * 8 - 9 * +
  57. 1 2 + 3 4 - 5 - 6 7 * * 8 * 9 + -
  58. 1 2 + 3 4 5 6 + * 7 8 + * 9 + * +
  59. 1 2 3 4 - 5 - 6 * 7 * + 8 * 9 - -
  60. 1 2 3 + - 4 5 + 6 / 7 8 * 9 * - *
  61. 1 2 3 / * 4 5 6 7 8 * * - - 9 * *
  62. 1 2 3 4 5 6 / 7 - * - 8 * + 9 * *
  63. 1 2 3 4 5 + - 6 * 7 * 8 * - + 9 -
  64. 1 2 3 4 - 5 - 6 7 * * 8 * 9 + - +
  65. 1 2 3 / * 4 5 - 6 7 * 8 * + 9 * *
  66. 1 2 3 4 5 + 6 * 7 * 8 * 9 - / / *
  67. 1 2 * 3 4 5 - 6 7 8 * * + / 9 / /
  68. 1 2 * 3 / 4 5 6 7 8 * * - - * 9 *
  69. 1 2 3 4 5 + - 6 * 7 * + 8 * - 9 +
  70. 1 2 3 4 - 5 - 6 7 * * 8 * - + 9 -
  71. 1 2 * 3 * 4 5 6 * 7 8 * + * 9 - *
  72. 1 2 * 3 / 4 5 - 6 7 * 8 * + * 9 *
  73. 1 2 3 4 5 - 6 7 8 * * + / / * 9 *
  74. 1 2 3 4 5 + - 6 7 * 8 * * 9 + - +
  75. 1 2 * 3 / 4 5 + 6 * 7 8 * * 9 - *
  76. 1 2 * 3 4 5 6 7 * 8 * - - / 9 / /
  77. 1 2 * 3 4 5 + 6 7 8 * * * 9 - / /
  78. 1 2 3 4 5 + - 6 7 8 * * * 9 + - +
  79. 1 2 3 4 5 + - 6 7 * * 8 * - 9 - +
  80. 1 2 * 3 4 5 + 6 * 7 * 8 * 9 - / /
  81. 1 2 + 3 4 5 6 7 8 * - - * + 9 * +
  82. 1 2 * 3 / 4 5 + 6 7 8 * * * 9 - *
  83. 1 2 3 4 5 + - 6 7 * 8 * * - + 9 -
  84. 1 2 3 4 - 5 - 6 * 7 8 * * 9 + - +
  85. 1 2 3 * 4 5 6 * 7 8 * + * 9 - * *
  86. 1 2 + 3 4 5 + - 6 7 * 8 * * - 9 -
  87. 1 2 + 3 + 4 5 6 * 7 8 * + * 9 - *
  88. 1 2 3 / 4 5 6 7 8 * * - - 9 * * *
  89. 1 2 + 3 4 5 + - 6 * 7 * 8 * - 9 -
  90. 1 2 3 / 4 5 + 6 * 7 8 * * 9 - * *
  91. 1 2 3 / 4 5 6 7 * 8 * - - * * 9 *
  92. 1 2 3 4 5 6 7 8 * * - - 9 * / / *
  93. 1 2 3 4 5 6 + * * 7 - 8 * * 9 + +
  94. 1 2 3 4 5 + - 6 7 8 * * * - + 9 -
  95. 1 2 3 4 - 5 - 6 * 7 * 8 * - 9 - +
  96. 1 2 + 3 4 5 + - 6 7 8 * * * 9 + -
  97. 1 2 * 3 / 4 5 6 7 * 8 * - - * 9 *
  98. 1 2 + 3 4 5 6 7 * 8 + + * + 9 * +
  99. 1 2 * 3 4 5 - 6 7 * 8 * + / 9 / /
  100. 1 2 + 3 4 - 5 - 6 7 * 8 * * - 9 -
  101. 1 2 3 4 5 - 6 7 8 * * + 9 * / / *
  102. 1 2 3 4 5 - 6 7 * 8 * + / / 9 * *
  103. 1 2 3 4 - 5 - 6 * 7 8 * * - + 9 -
  104. 1 2 3 + + 4 5 6 * 7 8 * + * 9 - *
  105. 1 2 + 3 4 - 5 - 6 7 8 * * * 9 + -
  106. 1 2 3 4 5 6 7 8 * * - - / / * 9 *
  107. 1 2 3 4 5 6 - 7 8 * + * + 9 * + +
  108. 1 2 3 4 5 - 6 7 * 8 * + / 9 / / *
  109. 1 2 3 / 4 5 - 6 7 * 8 * + * * 9 *
  110. 1 2 3 / * 4 5 - 6 7 * 8 * + * 9 *
  111. 1 2 3 4 5 6 7 * 8 * - - / / 9 * *
  112. 1 2 3 4 * 5 6 + * 7 - * 8 * + 9 +
  113. 1 2 3 / * 4 5 + 6 * 7 8 * * 9 - *
  114. 1 2 3 / 4 5 - 6 7 8 * * + * * 9 *
  115. 1 2 * 3 4 5 + 6 7 * 8 * * 9 - / /
  116. 1 2 3 4 5 6 7 * 8 * - - / 9 / / *
  117. 1 2 3 / * 4 5 + 6 7 8 * * * 9 - *
  118. 1 2 * 3 4 5 - 6 7 8 * * + 9 * / /
  119. 1 2 3 / 4 5 6 7 8 * * - - * 9 * *
  120. 1 2 3 4 + * + 5 6 - 7 8 + 9 * + *
  121. 1 2 3 4 - 5 - 6 7 * 8 * * - 9 - +
  122. 1 2 + 3 4 5 + - 6 * 7 8 * * 9 + -
  123. 1 2 3 4 - 5 - 6 7 8 * * * - 9 - +
  124. 1 2 3 / * 4 5 6 7 * 8 * - - * 9 *
  125. 1 2 * 3 4 5 6 7 * 8 * - - 9 * / /
  126. 1 2 3 4 5 6 7 8 * - - * + 9 * + +
  127. 1 2 3 4 5 6 / 7 8 * + * - + - 9 *
  128. 1 2 3 4 5 6 + * 7 8 + * 9 + * + +
  129. 1 2 3 4 5 + 6 7 8 * * * 9 - / / *
  130. 1 2 3 4 5 + - 6 7 * * 8 * 9 + - +
  131. 1 2 + 3 4 - 5 - 6 * 7 * 8 * - 9 -
  132. 1 2 3 / * 4 5 6 7 8 * * - - * 9 *
  133. 1 2 + 3 4 - 5 - 6 * 7 8 * * 9 + -
  134. 1 2 * 3 4 5 6 / 7 - * - 8 * + 9 *
  135. 1 2 3 4 5 6 / 7 - * - 8 * + * 9 *
  136. 1 2 * 3 / 4 5 + 6 7 * 8 * * 9 - *
  137. 1 2 * 3 4 5 - 6 7 8 * * + / / 9 *
  138. 1 2 * 3 / 4 5 - 6 7 8 * * + 9 * *
  139. 1 2 3 4 5 + * 6 + 7 * 8 - 9 * + +
  140. 1 2 3 4 5 + - 6 7 * * 8 * - + 9 -
  141. 1 2 3 4 5 + - 6 * 7 8 * * - 9 - +
  142. 1 2 3 / 4 5 + 6 * 7 * 8 * 9 - * *
  143. 1 2 * 3 / 4 5 + 6 * 7 * 8 * 9 - *
  144. 1 2 * 3 4 5 6 * 7 8 * + * 9 - * *
  145. 1 2 * 3 4 5 6 7 * 8 * - - / / 9 *
  146. 1 2 + 3 4 5 6 + 7 8 + * * 9 + * +
  147. 1 2 3 4 - 5 - 6 * 7 * 8 * 9 + - +
  148. 1 2 + 3 4 5 + - 6 7 * 8 * * 9 + -
  149. 1 2 * 3 4 5 - 6 7 * 8 * + 9 * / /
  150. 1 2 3 4 5 6 7 * + 8 + * + 9 * + +
  151. 1 2 3 4 5 + - 6 7 * * + 8 * - 9 +
  152. 1 2 + 3 4 5 + - 6 7 * * 8 * - 9 -
  153. 1 2 3 4 5 6 + * * 7 - 8 * * + 9 +
  154. 1 2 3 4 5 6 + * * 7 - * 8 * 9 + +
  155. 1 2 3 4 - 5 - 6 * 7 * 8 * - + 9 -
  156. 1 2 + 3 4 - 5 - 6 7 * * 8 * - 9 -
  157. 1 2 3 4 5 + - 6 * 7 * + 8 * 9 - -
  158. 1 2 3 4 * + + 5 6 - 7 8 + 9 * + *
  159. 1 2 * 3 4 5 + 6 7 * * 8 * 9 - / /
  160. 1 2 3 4 5 6 7 * 8 * - - 9 * / / *
  161. 1 2 3 4 5 6 + 7 8 + * * 9 + * + +
  162. 1 2 3 4 - 5 - 6 7 * 8 * * 9 + - +
  163. 1 2 3 / * 4 5 - 6 7 8 * * + 9 * *
  164. 1 2 3 / 4 5 + 6 7 * 8 * * 9 - * *
  165. 1 2 3 4 - 5 - 6 * 7 * + 8 * - 9 +
  166. 1 2 3 / * 4 5 + 6 7 * 8 * * 9 - *
  167. 1 2 * 3 4 5 - 6 7 * 8 * + / / 9 *
  168. 1 2 3 4 5 - 6 7 * 8 * + / / * 9 *
  169. 1 2 3 4 - 5 - 6 7 8 * * * 9 + - +
  170. 1 2 3 4 - 5 - 6 7 * * 8 * - 9 - +
  171. 1 2 3 4 - 5 - 6 7 * * + 8 * 9 - -
  172. 1 2 3 4 + * + 5 6 7 8 + 9 * - - *
  173. 1 2 3 / 4 5 + 6 7 8 * * * 9 - * *
  174. 1 2 3 4 * 5 6 + * 7 - 8 * * 9 + +
  175. 1 2 3 4 - 5 - 6 7 * 8 * * - + 9 -
  176. 1 2 * 3 4 5 6 7 8 * * - - / 9 / /
  177. 1 2 3 4 5 6 7 * 8 * - - / / * 9 *
  178. 1 2 3 4 - 5 - 6 7 8 * * * - + 9 -
  179. 1 2 3 / 4 5 6 7 * 8 * - - 9 * * *
  180. 1 2 + 3 4 5 + - 6 * 7 * 8 * 9 + -
  181. 1 2 - 3 - 4 5 + 6 / 7 8 9 * * - *
  182. 1 2 - 3 - 4 5 6 / 7 8 * + * + 9 *
  183. 1 2 3 / 4 5 6 7 8 * * - - * * 9 *
  184. 1 2 * 3 / 4 5 6 7 8 * * - - 9 * *
  185. 1 2 + 3 4 * + 5 6 - 7 8 + 9 * + *
  186. 1 2 + 3 4 - 5 - 6 7 * 8 * * 9 + -

たくさん ある なかで とくに
1 2 3 4 5 6 7 8 * * - - / / 9 * *
は いんしょうてき。1 から 8 まで いっきに ならべられるのも すごいし、たしざんを つかってないのも いい。おぼえやすい。

つぎは これを infix notation に へんかん。うえの しき だと、RPN を しらない ひとには 自慢 できないし。

ちなみに、演算を 全部 かっこで くくる、みたいに して へんかん すると うまく いかない。

たとえば 1 2 + 3 +1 2 3 + + は、それぞれ infix notation に へんかん すると ((1 + 2) + 3)(1 + (2 + 3)) に なって、かっこを てんかい すれば まったく おなじ しきに なる。

なので、たしざんには かっこを つけない、ひきざんは a - b の b に + か - が はいっていたら a - (b) に する、などの 処理を しながら へんかん していく。ちょっと 注意が 必要。

というわけで、へんかんの けっかは いかの 48 とおり。

  1. 1 * 2 / (3 / ((4 + 5) * 6 * 7 * 8 - 9))
  2. 1 * (2 / (3 / ((4 + 5) * 6 * 7 * 8 - 9)))
  3. 1 + 2 + (3 + 4 * (5 - (6 - 7 * 8))) * 9
  4. (1 - (2 + 3 - 4 * (5 / 6 + 7 * 8))) * 9
  5. 1 * (2 / ((3 / (4 - (5 - 6 * 7 * 8))) / 9))
  6. (1 - 2 - (3 - 4 * (5 / 6 + 7 * 8))) * 9
  7. 1 * (2 / (3 / ((4 - 5 + 6 * 7 * 8) * 9)))
  8. 1 + 2 + 3 * (4 * (5 + 6) * (7 + 8) + 9)
  9. (1 - (2 + 3)) * ((4 + 5) / 6 - 7 * 8 * 9)
  10. 1 * (2 / 3) * (4 - (5 - 6 * 7 * 8)) * 9
  11. 1 * (2 / 3) * ((4 + 5) * 6 * 7 * 8 - 9)
  12. 1 * 2 * 3 * (4 * (5 * 6 + 7 * 8) - 9)
  13. (1 - (2 + 3) + 4 * (5 / 6 + 7 * 8)) * 9
  14. 1 * (2 / (3 / (4 - (5 - 6 * 7 * 8)))) * 9
  15. 1 + 2 * (3 * 4 * (5 + 6) - 7) * 8 + 9
  16. (1 * 2 / (3 / (4 - 5 + 6 * 7 * 8))) * 9
  17. (1 * 2 + (3 - 4 * (5 / 6 - 7)) * 8) * 9
  18. 1 - ((2 + (3 - 4 - 5) * 6 * 7) * 8 - 9)
  19. 1 * (2 / (3 / (4 - 5 + 6 * 7 * 8))) * 9
  20. 1 + 2 + (3 + 4 * (5 + 6 * 7 + 8)) * 9
  21. (1 + 2 + 3 * 4) * (5 - 6 + (7 + 8) * 9)
  22. 1 * (2 / (3 / ((4 - (5 - 6 * 7 * 8)) * 9)))
  23. 1 * (2 + (3 - 4 * (5 / 6 - 7)) * 8) * 9
  24. 1 * 2 / (3 / ((4 - (5 - 6 * 7 * 8)) * 9))
  25. (1 + 2 + 3 * 4) * (5 - (6 - (7 + 8) * 9))
  26. (1 * 2 / 3) * ((4 + 5) * 6 * 7 * 8 - 9)
  27. (1 + 2 * (3 + 4)) * (5 - 6 + (7 + 8) * 9)
  28. 1 * 2 / ((3 / (4 - 5 + 6 * 7 * 8)) / 9)
  29. 1 + 2 + ((3 * (4 + 5) + 6) * 7 - 8) * 9
  30. 1 + 2 + (3 + 4 * (5 - 6 + 7 * 8)) * 9
  31. 1 * (2 / 3) * (4 - 5 + 6 * 7 * 8) * 9
  32. 1 + 2 - ((3 - (4 + 5)) * 6 * 7 * 8 + 9)
  33. 1 + 2 - (3 - (4 + 5)) * 6 * 7 * 8 - 9
  34. 1 - (2 + (3 - (4 + 5)) * 6 * 7) * 8 + 9
  35. (1 * 2 / (3 / (4 - (5 - 6 * 7 * 8)))) * 9
  36. (1 - 2 - 3 + 4 * (5 / 6 + 7 * 8)) * 9
  37. (1 + 2 + 3) * (4 * (5 * 6 + 7 * 8) - 9)
  38. 1 - ((2 + (3 - (4 + 5)) * 6 * 7) * 8 - 9)
  39. 1 * (2 / ((3 / (4 - 5 + 6 * 7 * 8)) / 9))
  40. (1 + 2 * (3 + 4)) * (5 - (6 - (7 + 8) * 9))
  41. 1 * 2 / (3 / ((4 - 5 + 6 * 7 * 8) * 9))
  42. 1 * 2 / ((3 / (4 - (5 - 6 * 7 * 8))) / 9)
  43. 1 + 2 - (3 - 4 - 5) * 6 * 7 * 8 - 9
  44. (1 * 2 / 3) * (4 - (5 - 6 * 7 * 8)) * 9
  45. 1 - (2 + (3 - 4 - 5) * 6 * 7) * 8 + 9
  46. (1 - 2 - 3) * ((4 + 5) / 6 - 7 * 8 * 9)
  47. (1 * 2 / 3) * (4 - 5 + 6 * 7 * 8) * 9
  48. 1 + 2 - ((3 - 4 - 5) * 6 * 7 * 8 + 9)

ふつうの しきは Google で かんたんに 確認 できるのが べんり。RPN も けいさんの けっかを 確認 できるように するべき だろうか。

この なかでは、やはり Knuth せんせいの ケーキに えらばれた
1 + 2 + 3 * (4 * (5 + 6) * (7 + 8) + 9)
が いちばん いんしょうてき。たしざんと かけざん しか つかってない。

たしざんと かけざん だけの しき は、もう ひとつ
1 + 2 + (3 + 4 * (5 + 6 * 7 + 8)) * 9
が あるけれど、こちらは 8の うしろに かっこが ふたつ 連続で ならぶ のが うつくしくない。


って、しゅんは とっくに すぎてる 話題 だけれど、今年は まだ なにも かいてなかったので、とりあえず、こんな かんじで スタートを きっておきます。文句が あったら "@n (cont)" あてに twitlonger けいゆで 連絡 ください。さくっと block します。わ

No comments:

Post a Comment