Combination 생성하기

Tags:

루비로 combination 생성하는 코드를 짜봤습니다. 최대한 효율적으로 한다고 했는데 결국은 수형도 (tree diagram) 그리듯이 만들어 버린;;

def v_0_set(list, r)
    v_i_set(list, -1, 0, r)
end

def v_i_set(list, prev_val, idx, r)
    start_idx = prev_val + 1
    end_idx = (list.size - 1) - (r - 1 - idx)

    (start_idx..end_idx).inject([]) do |memo, val|
        memo << &#91;val&#93;
    end
end

def gen_comb(list, r)
    current_set = v_0_set(list, r)
    for i in (1..r-1)
        current_set = gen_comb_with_previous_value_set(list, current_set, i, r)
    end

    current_set.map do |idx|
        idx.map { |i| list&#91;i&#93; }
    end
end

def gen_comb_with_previous_value_set(list, prev_set, idx, r)
    prev_set.inject(&#91;&#93;) do |memo, prev_val|
        memo += cart_prod(v_i_set(list, prev_val&#91;-1&#93;, idx, r), prev_val)
    end
end

def cart_prod(list, val)
    list.inject(&#91;&#93;) do |memo, i|
        memo << val + i
    end
end

list = &#91;11,12,13,14,15&#93;
puts gen_comb(list, 1).inspect
puts gen_comb(list, 2).inspect
puts gen_comb(list, 3).inspect
&#91;/code&#93;

결과는

&#91;code&#93;
C:\tmp>ruby comb_gen.rb
[[11], [12], [13], [14], [15]]
[[11, 12], [11, 13], [11, 14], [11, 15], [12, 13], [12, 14], [12, 15], [13, 14], [13, 15], [14, 15]]
[[11, 12, 13], [11, 12, 14], [11, 12, 15], [11, 13, 14], [11, 13, 15], [11, 14,15], [12, 13, 14], [12, 13, 15], [12, 14, 15], [13, 14, 15]]

C:\tmp>

Comments

One response to “Combination 생성하기”

  1. 공성식 Avatar
    공성식

    음. 이런 류의 문제는 recursive하게 작성하면 좀더 간단해지더라구요.
    약간 지저분하지만 제가 한번 만들어봤습니다.
    (Combination은 배열보다는 셋에 더 적합합니다만,
    그냥 배열을 이용하였고, 원소들이 중복되지 않는다는 가정을 하였습니다.)

    def comb(a, n)
    return a.inject([]) {|m, i| m.push [i]} if n == 1
    result = []
    a[0..-n].each_with_index do |i, idx|
    comb(a[idx + 1..-1], n – 1).each {|ar| result.push(ar.unshift(i))}
    end
    result
    end

    each_with_index를 inject로 바꾸면 더 간단해질 텐데,
    그렇게 하면 내부에서 index를 찾아야 하므로 그냥 놔뒀습니다.
    혹시 더 좋은 방법이 있으면 깔끔하게 바꿔주세요.

Leave a Reply

Your email address will not be published. Required fields are marked *