新手问题 数字分组 2

bluexuemei · 2014年04月30日 · 最后由 bluexuemei 回复于 2014年05月01日 · 3018 次阅读

0-9 共 10 个数字,分为 5 组(每组两个数字,小到大排列),要求后一组数字大于前一组数字,生成像 01-23-45-67-89 这样的组合,列出所有的组合。

-_-#又来一个……其实可以放一起讨论吧……

(0..9).to_a.permutation.map {|a|
  a.each_slice(2).map {|x| x.sort.join}
} .select {|a|
  a.each_cons(2).all? {|x, y| x < y }
}.uniq

效率就……不要想了……

……刚才漏看个条件……

2 楼 已删除

后一组比前一组大,是指两个数字的 sum 大,还是挨个比较大 (第一个大第二个就忽略了),还是全部大 (第一个和第二个都大)? 如何是和的话,组合就相当相当的多了。

假设都 2 个都必须大:

:m Data.List

let pairs = [(a,b) | a <- [0..9], b <- [0..9], a < b]
let result = [(x,y,z,m,n) | x <- pairs, y <- pairs, z <- pairs, m <- pairs, n <- pairs, 
               (\(h,t) (p,q) -> (h < p && t < q)) x y,
               (\(h,t) (p,q) -> (h < p && t < q)) y z,
               (\(h,t) (p,q) -> (h < p && t < q)) z m,
               (\(h,t) (p,q) -> (h < p && t < q)) m n,
               (sort $ concat $ map (\(h,t) -> [h,t]) [x,y,z,m,n]) == [0..9]]
Prelude Data.List> result 
[((0,1),(2,3),(4,5),(6,7),(8,9)),((0,1),(2,3),(4,5),(6,8),(7,9)),((0,1),(2,3),(4,6),(5,7),(8,9)),((0,1),(2,3),(4,6),(5,8),(7,9)),((0,1),(2,3),(4,7),(5,8),(6,9)),((0,1),(2,4),(3,5),(6,7),(8,9)),((0,1),(2,4),(3,5),(6,8),(7,9)),((0,1),(2,4),(3,6),(5,7),(8,9)),((0,1),(2,4),(3,6),(5,8),(7,9)),((0,1),(2,4),(3,7),(5,8),(6,9)),((0,1),(2,5),(3,6),(4,7),(8,9)),((0,1),(2,5),(3,6),(4,8),(7,9)),((0,1),(2,5),(3,7),(4,8),(6,9)),((0,1),(2,6),(3,7),(4,8),(5,9)),((0,2),(1,3),(4,5),(6,7),(8,9)),((0,2),(1,3),(4,5),(6,8),(7,9)),((0,2),(1,3),(4,6),(5,7),(8,9)),((0,2),(1,3),(4,6),(5,8),(7,9)),((0,2),(1,3),(4,7),(5,8),(6,9)),((0,2),(1,4),(3,5),(6,7),(8,9)),((0,2),(1,4),(3,5),(6,8),(7,9)),((0,2),(1,4),(3,6),(5,7),(8,9)),((0,2),(1,4),(3,6),(5,8),(7,9)),((0,2),(1,4),(3,7),(5,8),(6,9)),((0,2),(1,5),(3,6),(4,7),(8,9)),((0,2),(1,5),(3,6),(4,8),(7,9)),((0,2),(1,5),(3,7),(4,8),(6,9)),((0,2),(1,6),(3,7),(4,8),(5,9)),((0,3),(1,4),(2,5),(6,7),(8,9)),((0,3),(1,4),(2,5),(6,8),(7,9)),((0,3),(1,4),(2,6),(5,7),(8,9)),((0,3),(1,4),(2,6),(5,8),(7,9)),((0,3),(1,4),(2,7),(5,8),(6,9)),((0,3),(1,5),(2,6),(4,7),(8,9)),((0,3),(1,5),(2,6),(4,8),(7,9)),((0,3),(1,5),(2,7),(4,8),(6,9)),((0,3),(1,6),(2,7),(4,8),(5,9)),((0,4),(1,5),(2,6),(3,7),(8,9)),((0,4),(1,5),(2,6),(3,8),(7,9)),((0,4),(1,5),(2,7),(3,8),(6,9)),((0,4),(1,6),(2,7),(3,8),(5,9)),((0,5),(1,6),(2,7),(3,8),(4,9))
]
Prelude Data.List> 
Prelude Data.List> length result 
42
def combinations_string(a,n)
  return unless a.size == n.inject(:+)
  s=a.combination(n[0]).to_a
  n[1..-1].each do |i|
    s.length.times do
      x = s.pop
      (a-x).combination(i){|b| s.unshift(x+b) if x[-i..-1].join < b.join}
    end
  end
  s.map {|t| n.map{|r| t.shift(r).join }.join('-')}
end

combinations_string([*0..9],[2,2,2,2,2])

时间是 0.139533 s,个数是 945。

puts combinations_string([*0..5],[2,2,2]).join(', ')

01-25-34, 01-24-35, 01-23-45, 02-15-34, 02-14-35, 02-13-45, 03-15-24, 03-14-25, 03-12-45, 04-15-23, 04-13-25, 04-12-35, 05-14-23, 05-13-24, 05-12-34

#3 楼 @debugger 是后一组的两位数大于前一组的两位数,组合共 945 个

#5 楼 @bluexuemei 是这样啊,把条件改成 ((h,t) (p,q) -> (h * 10 + t < p * 10 + q)) x y,后我试了试确实是 945 个,你这是做科研还是做游戏啊?

ghci>length result
945
ghci>

#6 楼 @debugger 只是练习而已,大师的代码好深奥啊,看不懂。

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