新手问题 求数组的子集

bluexuemei · 2014年05月04日 · 最后由 piecehealth 回复于 2014年05月04日 · 2917 次阅读

a=[*0..9],求 a 的所有子集

1.upto(a.size) {|i| a.combination(i).map {|sub_arr| puts sub_arr.to_a.join(', ')}}

#1 楼 @piecehealth 这个算法不知道效率如何,用递归怎么写呢?

#2 楼 @bluexuemei

a = [*0..9]

def c arr, n
    return arr.map {|i| [i]} if n == 1
    rets = []
    arr.each_with_index do |ele, i|
        rets += c(arr[i + 1, arr.size - i - 1], n - 1).map {|a| [ele, *a]}
    end
    rets
end

def all_sub_arrs arr
    rets = []
    1.upto(arr.size) do |i|
        rets += c(arr, i)
    end
    rets
end

require 'benchmark'

Benchmark.bm do |x|
    x.report do
        result = []
        1.upto(a.size) {|i| a.combination(i).each {|sub_arr|  result << sub_arr.to_a}}
    end
    x.report {result = all_sub_arrs a}
end

自己实现 combination 肯定没有 ruby 自带的快,Array 内置的方法都是 c 写的。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号