[ruby-dev:40601] Re: [ruby-list:46898] 重複組合せは組込みにならないのでしょうか？

遠藤です。

2010年3月12日15:53 Yukihiro Matsumoto <[e-mail]>:
> In message "Re: [ruby-dev:40597] Re: [ruby-list:46898] 重複組合せは組込みにならないのでしょうか？"
>   on Fri, 12 Mar 2010 15:49:24 +0900, "KISHIMOTO, Makoto" <[e-mail]> writes:
>
> |> ソートルーチンのテストデータを生成しようとして思ったのですが、
> |> 順列と組合せは組込みになりましたが、重複組合せは組込みにならないのでしょうか？
> |
> |組込みの重複順列と重複組合せを実装してみました。

おおすばらしい。
パッチ書いて賛成票入れようと思っていたのですが、もたもたしていたら
先を越されました。


> うーん、重複順列とか重複組み合わせとか、実際どのように使って、
> 組み込まれてるとどのくらい嬉しいんですかね。ちょっとピンとこ
> ないんですが。

重複順列は brute force でめちゃくちゃ便利です。
例えば、英小文字 3 文字からなるパスワードでログインを試みるとか、

  ("a".."z").to_a.repeated_permutation(5).find {|s| login(s.join) }

あやしい文字列を生成して Ruby のパーサのバグを探すとか、

  %w(( ) $ ` ' | & =).repeated_permutation(5) do |s|
    begin; eval(p(s.join)); rescue Exception; end
  end

が、こんなに簡単に書けます。

repeated_permutation なしで書くとしたら

  ary.product(ary, ary, ary, ary).each {|s| ... }

などとできなくはないですが、少しわかりにくい上に、product は配列を
返してしまうという致命的な問題があるので、実用になりません。

重複組み合わせの用途はぱっとは思いつきませんが、いかにもパズルで
必要になりそうです (その場合は並び換えの数も合わせて知りたいかも) 。


> > 2つ目のパッチは、重複でない組合せに引数なしを追加するものです。
> > （重複でない組合せだけ、引数なしを受け付けない（あってもあまり意味ないんですが）
> > というのも変かなという気がするので）

permutation の場合は

  - permutation の言葉だけで全要素の並び換えが期待される
  - ary = [...]; ary.permutation(ary.length) は使い道がたくさんある

のですが、combination の場合は

  - combination だけでは曖昧 (任意個の組み合わせか？)
  - ary = [...]; ary.combination(ary.length) は使い出がない

ので、入れるべきでないと思います。あえて入れるのであれば、

  (0...ary.length).flat_map {|n| ary.combination(n) }

という意味の方が (私の) 直感にはあいますし、使い出もありそうです。

同様に、repeated_permutation/combination のデフォルト引数にも反対
です。

-- 
Yusuke ENDOH <[e-mail]>