ことの始まり
先日，AtCoderのこの問題をRubyで解きました（提出したコードはこれ）。
ポイント（という程のものではありませんが）は，RubyのArray#repeated_permutationというメソッドです。配列に対して，その要素たちからなる「重複順列」を返します。
repeated_permutation.rb
[1,2].repeated_permutation(3).each{|i|
p i
}
$ ruby repeated_permutation.rb
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 2, 2]
[2, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 2, 2]
AtCoderの問題では，配列["", "+"]に対してrepeated_permutationを用いて生成した順列を，与えられた自然数（10進表示）の数字の間に入れ，最後にevalし，そうやって得られた数たちの和を求めました。
小町算へ
その後，「このロジックって小町算に使えるよね」と気づき，やってみました。
komachizan1.rb
input = "123456789".chars
result = []
["", "+", "-", "*"].repeated_permutation(input.size - 1).each{|ops|
str = input.zip(ops).join
result.push(str)
result.push("-" + str)
}
result.select{|i| eval(i) == 100}.each_with_index{|s, i|
puts "#{i+1} : #{s} = 100"
}
input.zip(ops).joinの部分で，input（["1", "2", "3", "4", "5", "6", "7", "8", "9"]）の間に演算子の並びops（["+", "-", "+", "*", "-", "", "*", "*", ""]など）を挿入していっています。- また，-1から始まるパターンも入れています。
$ ruby komachizan1.rb
1 : 123+45-67+8-9 = 100
2 : -123+45*6-7*8+9 = 100
3 : 123+4-5+67-89 = 100
4 : 123+4*5-6*7+8-9 = 100
5 : 123-45-67+89 = 100
6 : -123-4+5*6*7+8+9 = 100
7 : 123-4-5-6-7+8-9 = 100
8 : -12+34+5-6+7+8*9 = 100
9 : 12+34+5*6+7+8+9 = 100
10 : 12+34-5+6*7+8+9 = 100
11 : 12+34-5-6+7*8+9 = 100
12 : 12+34-5-6-7+8*9 = 100
13 : 12+3+4+5-6-7+89 = 100
14 : 12+3-4+5+67+8+9 = 100
15 : 12+3*45+6*7-89 = 100
16 : 12+3*4+5+6+7*8+9 = 100
17 : 12+3*4+5+6-7+8*9 = 100
18 : 12+3*4-5-6+78+9 = 100
19 : 12-3+4*5+6+7*8+9 = 100
20 : 12-3+4*5+6-7+8*9 = 100
21 : -12-3-4+5+6*7+8*9 = 100
22 : 12-3-4+5-6+7+89 = 100
23 : 12-3-4+5*6+7*8+9 = 100
24 : 12-3-4+5*6-7+8*9 = 100
25 : 12*3-4+5-6+78-9 = 100
26 : 12*3-4-5-6+7+8*9 = 100
27 : -12*3-4*5+67+89 = 100
28 : 12*3-4*5+67+8+9 = 100
29 : 1+234-56-7-8*9 = 100
30 : 1+23-4+56+7+8+9 = 100
31 : 1+23-4+5+6+78-9 = 100
32 : 1+23-4-5+6+7+8*9 = 100
33 : -1+23*4+56-7*8+9 = 100
34 : 1+23*4+5-6+7-8+9 = 100
35 : -1+23*4+5-6-7+8+9 = 100
36 : -1+23*4-56+7*8+9 = 100
37 : -1+23*4-56-7+8*9 = 100
38 : 1+23*4-5+6+7+8-9 = 100
39 : -1+23*4-5+6+7-8+9 = 100
40 : 1+2+34-5+67-8+9 = 100
41 : 1+2+34*5+6-7-8*9 = 100
42 : -1+2+34*5-6+7-8*9 = 100
43 : -1+2+34*5-6-7*8-9 = 100
44 : 1+2+3+4+5+6+7+8*9 = 100
45 : -1+2+3+4*5-6-7+89 = 100
46 : -1+2+3+4*5*6-7-8-9 = 100
47 : 1+2+3-45+67+8*9 = 100
48 : 1+2+3-4+5+6+78+9 = 100
49 : 1+2+3-4*5+6*7+8*9 = 100
50 : 1+2+3*4-5-6+7+89 = 100
51 : -1+2-3+4+5+6+78+9 = 100
52 : 1+2-3*4+5*6+7+8*9 = 100
53 : 1+2-3*4-5+6*7+8*9 = 100
54 : 1+2*34-56+78+9 = 100
55 : -1+2*3+45+67-8-9 = 100
56 : 1+2*3+4+5+67+8+9 = 100
57 : -1+2*3+4*5+6+78-9 = 100
58 : 1+2*3+4*5-6+7+8*9 = 100
59 : -1+2*3-4+5*6+78-9 = 100
60 : 1+2*3-4-5+6+7+89 = 100
61 : -1+2*3*4+5*6+7*8-9 = 100
62 : 1-23+4*5+6+7+89 = 100
63 : 1-23-4+5*6+7+89 = 100
64 : 1-23-4-5+6*7+89 = 100
65 : -1-23*4+5*6*7-8-9 = 100
66 : 1-2+3+45+6+7*8-9 = 100
67 : 1-2+3*4+5+67+8+9 = 100
68 : 1-2+3*4*5+6*7+8-9 = 100
69 : -1-2+3*4*5+6*7-8+9 = 100
70 : 1-2+3*4*5-6+7*8-9 = 100
71 : 1-2-34+56+7+8*9 = 100
72 : 1-2-3+45+6*7+8+9 = 100
73 : 1-2-3+45-6+7*8+9 = 100
74 : 1-2-3+45-6-7+8*9 = 100
75 : 1-2-3+4*5+67+8+9 = 100
76 : -1-2*3+4+56+7*8-9 = 100
77 : 1-2*3+4*5+6+7+8*9 = 100
78 : 1-2*3-4+5*6+7+8*9 = 100
79 : 1-2*3-4-5+6*7+8*9 = 100
80 : -1-2*3*4+56+78-9 = 100
81 : 1*234+5-67-8*9 = 100
82 : -1*234+5*67+8-9 = 100
83 : 1*23+4+5+67-8+9 = 100
84 : -1*23+4+5+6*7+8*9 = 100
85 : 1*23-4+5-6-7+89 = 100
86 : 1*2+34+56+7-8+9 = 100
87 : 1*2+34+5+6*7+8+9 = 100
88 : -1*2+34+5-6+78-9 = 100
89 : 1*2+34+5-6+7*8+9 = 100
90 : 1*2+34+5-6-7+8*9 = 100
91 : -1*2+34-5-6+7+8*9 = 100
92 : -1*2+34*5-67+8-9 = 100
93 : 1*2+3+45+67-8-9 = 100
94 : -1*2+3+4+5-6+7+89 = 100
95 : -1*2+3+4+5*6+7*8+9 = 100
96 : -1*2+3+4+5*6-7+8*9 = 100
97 : 1*2+3+4*5+6+78-9 = 100
98 : -1*2+3-4+56+7*8-9 = 100
99 : 1*2+3-4+5*6+78-9 = 100
100 : -1*2+3*4+5+6+7+8*9 = 100
101 : 1*2+3*4+5-6+78+9 = 100
102 : -1*2-34+5+6*7+89 = 100
103 : 1*2-3+4-5+6+7+89 = 100
104 : -1*2-3+4*5+6+7+8*9 = 100
105 : 1*2-3+4*5-6+78+9 = 100
106 : -1*2-3-4+5*6+7+8*9 = 100
107 : -1*2-3-4-5+6*7+8*9 = 100
108 : 1*2*34+56-7-8-9 = 100
109 : 1*2*3+4+5+6+7+8*9 = 100
110 : 1*2*3-45+67+8*9 = 100
111 : 1*2*3-4+5+6+78+9 = 100
112 : 1*2*3-4*5+6*7+8*9 = 100
113 : 1*2*3*4+5+6+7*8+9 = 100
114 : 1*2*3*4+5+6-7+8*9 = 100
115 : 1*2*3*4-5-6+78+9 = 100
全部で115個見つかりました。
割り算
ただ，これでは割り算が入っていません。
1/2*3/4*56+7+8*9 = 100
のようなものもあるので，こういうものも含めて数え上げましょう。
ただ，komachizan1.rb において単純に["", "+", "-", "*"]の部分を["", "+", "-", "*", "/"]にするだけではダメです。整数の割り算では余りは切り捨てられて商のみ返すので，1/2*3/4*56+7+8*9は100ではなく79となってしまいます（0*0*56+7+8*9）。
not_100_but_79.rb
p eval("1/2*3/4*56+7+8*9")
$ ruby not_100_but_79.rb
79
じゃあはじめから数字をfloatにキャストしておけばいいかというと，それもうまくいきません。1と2の間に演算子を入れない場合には12になってほしいのですが，1.0と2.0をそのままつなげても12にならないからです。
次回「Rubyで小町算（その２）」で，この問題を回避する方法を考えたいと思います。
追記１（2016年12月3日）
配列inputの要素の間に配列opsを挟み込んでいく部分を
str = input.zip(ops).flatten.compact.join
と記述していましたが，この場合最後のjoinのおかげでflattenとcompactは不要であると，@scivolaさんに教えていただきました。ありがとうございます！
追記２（2016年12月3日）
割り算の問題はrequire "mathn"するだけで解決されると，これまた@scivolaさんに教えていただきました。重ね重ね，ありがとうございます！
当初は
e = result.map{|s|
s.gsub(/(\d)([\/\*+-])/,'\1.0\2')+".0"
}
としてからevalしようと考えていました。カッコ悪いですね…。
というわけで，「Rubyで小町算（その２）」では別のネタを考えなければならなくなりました。笑