Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

順列を求める

世界で闘うプログラミング力を鍛える150問 トップIT企業のプログラマになるための本』を少しずつ解いています。第9章の問題9.5は、

ある文字列の、すべての順列を求めるメソッドを書いてください。

という問題です。
Project Eulerでも順列を扱う問題には幾度か出会っており、その度に自分で順列を求めるメソッドを作らないといけないなと思ってはいたのですが、

  • 再帰には苦手意識があったり、
  • Rubyには Array#permutation がある

ので、今までずっと後回しにしてきました。
実際作ってみると行数はたいしたことはないのですが、頭が混乱して大変でした。

q9_5.rb

# -*- coding: utf-8 -*-
class Array
  def my_permutation tmp = [], ans = []
    if self.size == 0
      ans << tmp
    else
      self.each {|c|
        (self-[c]).my_permutation tmp+[c], ans
      }
    end
    ans
  end
end

require 'pp'
pp "abc".chars.my_permutation

実行結果

$ ruby q9_5.rb
[["a", "b", "c"],
 ["a", "c", "b"],
 ["b", "a", "c"],
 ["b", "c", "a"],
 ["c", "a", "b"],
 ["c", "b", "a"]]