かせいさんとこ

重複を許可する配列の組み合わせを返す

ruby

Array#combination だと、重複は許可されないので自作

仕様

• サイズn の重複を許可した組み合わせを返す
• 同一値の重複は許可するけど、順序が異なるだけの組み合わせは返さない
  • [1,1,2] があったら、[1,2,1]や、[2,1,1] は返さない

コード

class Array
  def duplicate_combination(max_depth)
    b([], 0, max_depth).map {|obj| obj.sort }.uniq
  end

  def b(buf, depth, max_depth, result = [])
    depth = depth + 1
    self.each do |k|
      new_buf = (buf + [k]).flatten
      if max_depth > depth
        b(new_buf, depth, max_depth, result)
      else
        result << new_buf
      end
    end
    result
  end
  private :b
end

使い方

p [1,2,3,4,5].duplicate_combination(3)
# [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 5], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 3], [1, 3, 4], [1, 3, 5], [1, 4, 4], [1, 4, 5], [1, 5, 5], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 2, 5], [2, 3, 3], [2, 3, 4], [2, 3, 5], [2, 4, 4], [2, 4, 5], [2, 5, 5], [3, 3, 3], [3, 3, 4], [3, 3, 5], [3, 4, 4], [3, 4, 5], [3, 5, 5], [4, 4, 4], [4, 4, 5], [4, 5, 5], [5, 5, 5]]

そんなかんじ

Permalink | コメント(2) | トラックバック(0)