Ruby 求排列组合有没有简便的方法?

yakczh · 2015年08月13日 · 最后由 arth 回复于 2015年08月14日 · 3559 次阅读

比如求 1 到 12 中间 相加之和等于 12 的组合

for a in (1..11) do
  for b in (1..11) do
     for c in (1..11) do
        for d in (1..11) do
        for e in (1..11) do
        for f in (1..11) do




for i in (1..11) do
  for j in (1..11) do
     for k in (1..11) do
        for l in (1..11) do
            for m in (1..11) do
                for n in (1..11) do


 if a+b+c+d+e+f+i+j+k+l+m+n ==12  then
         print           10.chr,a,'+',b,'+',c,'+',d,'+',e,'+',f,'+'i,'+',j,'+',k,'+',l,'+',m,'+',n,'= 12'
     end
end
end
end
end
end
end
end
end
end
end
end
end


如果是 24 呢?

你这样的算法只能算出 n 个 1 相加的结果吧

(1..12).map{|i| (1..12).to_a.combination(i).select{|a| a.inject(&:+) == 12 } }
=> [[[12]], [[1, 11], [2, 10], [3, 9], [4, 8], [5, 7]], [[1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5]], [[1, 2, 3, 6], [1, 2, 4, 5]], [], [], [], [], [], [], [], []]

arr0 =[] arr1=[]

for a in 1..12 b = 12-a arr << a arr << b end

for i in 0.. 11 print "#{arr0[i]},#{arr1[i]}" end

这样子行么?

刚发现,不是两数之和,呆了。。。被你“相加”迷惑了,这是“累加”啊。。。

(1..12).inject([]){|s,i| s + (1..12).to_a.combination(i).select{|a| a.inject(&:+) == 12 }}
=> [[12], [1, 11], [2, 10], [3, 9], [4, 8], [5, 7], [1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5], [1, 2, 3, 6], [1, 2, 4, 5]]

无残留版

数硬币问题 http://rosettacode.org/wiki/Count_the_coins#Ruby

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

如果你用 Haskell:

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

好吧我哪有这么牛逼,其实是抄的

http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

楼主贴出这样的代码格式,你们怎么能忍??

2.1.2 :035 > (1..12).each{|i| (1..12).to_a.combination(i).map{|x| print x if x.inject(&:+)==12 } } [12][1, 11][2, 10][3, 9][4, 8][5, 7][1, 2, 9][1, 3, 8][1, 4, 7][1, 5, 6][2, 3, 7][2, 4, 6][3, 4, 5][1, 2, 3, 6][1, 2, 4, 5] => 1..12

可以用递归

9 楼 已删除
10 楼 已删除

#7 楼 @est 输出结果中怎么没有 puts [1,1,1,1,1,1,1,1,1,1,1,1] [2,2,2,2,2,2]. [3,3,3],[4,4,4,4],[6,6] 这些

#11 楼 @yakczh 因为人家不会连击...

可以自动生成上述代码,然后 eval

x=12
s=(1..x).map{|t|"(0..#{x-1}).each{|x#{t}|"}.join
ary=(1..x).map{|i|"x#{i}"}
eval s+"print "+ary.join(",',',")+',"\n" if '+ary.join("+")+"==#{x}"+"}"*x

#11 楼 @yakczh 允许重复取出 1-12 里的数么?

#14 楼 @est

(12) (1,11) (11,1) (2, 10) (10,2) (3, 9) (9, 3) (4, 8) (8,4) (5, 7) (7,5) (6, 6) (1, 1, 10) (1,10,1) (10,1,1) ...

这种的

按全排列算的话 (6,6) 算一条 (1, 11),(11,1 ) 应该算两条

#15 楼 @yakczh 那就是全排列了。把我代码里 combination 改成 permutation 就可以了。

(1..12).each{|i| (1..12).to_a.permutation(i).map{|x| print x if x.inject(&:+)==12 } }

使用回溯法。dfs 即可。很简单,帮楼主写了一个。试试看。


def sum_array_equals_to(target)
  elements=[]
  target.times{|i| elements<<i+1}
  result=[]
  dfs(target,0,[],elements,result)
  result.uniq
end

def dfs(target,curSum,curArray,elements,result)
  result<<curArray.sort if target==curSum
  elements.each do |e|
    if curSum+e<=target
      elements-=[e]
      dfs(target,curSum+e,curArray+[e],elements,result)
      elements+=[e]
    end
  end
end
p sum_array_equals_to(6)

f #18 楼 @arth 全排列 怎么写?

#19 楼 @yakczh leetcode 中有这道题,你可以在我的 github 中找。欢迎围观我发表的那个刷题帖。

#19 楼 @yakczh (1..12).each{|i| (1..12).to_a.repeated_permutation(i).map{|x| print x if x.inject(&:+)==12 } }

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