nekoTheShadow’s diary

技術ブログとして始めたはずが、読書&愚痴ブログになりました(´・ω・`)

javascriptでよりよい順列を。

以前「javascriptで順列」という記事を書きましたが、今日はその改良編です。

rubyにはpermutationというメソッドがあり、簡単に順列が取得できます。
今日はこれをまるぱくりしようということです。

p ["a","b","c","d"].permutation(3).to_a
  =>[["a", "b", "c"], ["a", "b", "d"], ["a", "c", "b"], ["a", "c", "d"],
     ["a", "d", "b"], ["a", "d", "c"], ["b", "a", "c"], ["b", "a", "d"], 
     ["b", "c", "a"], ["b", "c", "d"], ["b", "d", "a"], ["b", "d", "c"], 
     ["c", "a", "b"], ["c", "a", "d"], ["c", "b", "a"], ["c", "b", "d"], 
     ["c", "d", "a"], ["c", "d", "b"], ["d", "a", "b"], ["d", "a", "c"],
     ["d", "b", "a"], ["d", "b", "c"], ["d", "c", "a"], ["d", "c", "b"]]

ちなみにrubyのpermutationは配列に同じ値があったときは別のものとみなすのですが、その仕様ももちろんぱくります。

p ["a","a","b"].permutation(2).to_a
  => [["a", "a"], ["a", "b"], ["a", "a"], ["a", "b"], ["b", "a"], ["b", "a"]]

まとめるとこんなところ。

  • 配列からn個の要素を選んだときの順列を列挙する
    • n個は引数で取得する
  • Arrayのクラスメソッド
  • 配列に同じ値があったときは別のものとみなす
    • おそらく配列の要素ではなく、インデックスで順列を生成しているため

また、実装イメージとしては、

[2]   => 2はいれることができない   => 1,3,4はいれることができる => [2,1],[2,3],[2,4]
[2,1] => 1,2は入れることができない => 3,4はいれることができる   => [2,1,3],[2,1,4]

という感じ。
配列に足せるものを足していくというかなんというか。

案外あっさりできました。
問題は利用する状況があまりなさそうということぐらい(´・ω・`)