🍶組み合わせを列挙するアルゴリズムについて(Ruby)

arr = [1, 2, 3, 4, 5]

p arr.combination(2).to_a


# OUTPUT

[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

class Array

  # EXAMPLE: [1.2.3.4].combination_array(3) => [[1,2,3], [1,2,4], [1,3,4], [2,3,4]]

  def combination_array(comb_size)

    return [] if comb_size > size # 4C5のようなものは空を返す

    return [] if comb_size == 0 # 4C0のようなものは空を返す

    return [self] if comb_size == size

    return map { |e| [e] } if comb_size == 1


    ret = []

    (0..size - comb_size).each do |i|

      picked = self[i]

      rest = self[i + 1..-1]

      rest.combination_array(comb_size - 1).each do |c|

        ret << [picked] + c

      end

    end

    ret

  end

end

if $PROGRAM_NAME == __FILE__

  p %i[asahi kirin sapporo suntory].combination_array(2)

  # 重複がない時(既存メソッドとの比較)

  p [1, 2, 3, 4, 5, 6, 7, 8, 9].combination_array(3) == [1, 2, 3, 4, 5, 6, 7, 8, 9].combination(3).to_a

  # 重複がある時(既存メソッドとの比較)

  p [1, 2, 3, 4, 5, 6, 1, 8, 3].combination_array(4) == [1, 2, 3, 4, 5, 6, 1, 8, 3].combination(4).to_a

end

## OUTPUT

[[:asahi, :kirin], [:asahi, :sapporo], [:asahi, :suntory], [:kirin, :sapporo], [:kirin, :suntory], [:sapporo, :suntory]]

true

true