repeated_combination

Ruby の Array#repeated_combination は重複を許す組み合わせを返すメソッドだ(厳密にいうとEnumerator を返す)。
次のブログ記事で見つけた。

 cf. 続:Haskell/Clojureでrepeated_combinationを実装してみる – Programmer’s Note

これを Go でやってみよう、ということで Haskell のコードを参考に作ってみた。

ところが、実行結果が Array#repeated_combination と合わない。
上のコードの実行結果はこう。

^o^ > go run repeated_combination.go
[[1 1 1] [1 1 2] [1 1 3] [1 2 1] [1 2 2] [1 2 3] [1 3 1] [1 3 2] [1 3 3] [2 1 1] [2 1 2] [2 1 3] [2 2 1] [2 2 2] [2 2 3] [2 3 1] [2 3 2] [2 3 3] [3 1 1] [3 1 2] [3 1 3] [3 2 1] [3 2 2] [3 2 3] [3 3 1] [3 3 2] [3 3 3]]

対して Array#repeated_combination はこう。

irb(main):001:0> [1,2,3].repeated_combination(3).to_a
=> [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]]

順列ではなく組み合わせなので、Array#repeated_combination では例えば [1,1,2] と [1,2,1] と [2,1,1] を同じものとしているのに対して、Go のコードでは別のものとして数え上げてしまっている。
そこで改良を加えたのがこれだ。

実行結果。

^o^ > go run repeated_combination2.go
[[1 1 1] [1 1 2] [1 1 3] [1 2 2] [1 2 3] [1 3 3] [2 2 2] [2 2 3] [2 3 3] [3 3 3]]

今度はうまくいった。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です