Ruby 一道编程题

fsword · 2012年10月30日 · 最后由 hegwin 回复于 2012年11月02日 · 3545 次阅读

问题: 对给定的数组,拆分为指定个数的子数组,要求尽可能平均

我的实现是这样:

require 'matrix'
def split_group(arr, n)
  Matrix.columns( 
      (arr + [nil] * (n - arr.size % n)).each_slice(n).to_a 
  ).to_a.map(&:compact)
end

求更好的做法

如果没有别的限制,那么每个子数组仅一个元素就最平均了吧 - - 因为任意自然数都肯定能被 1 整除。

#1 楼 @5long 子数组个数是给定的,已经补充了原帖

Matrix.columns(x).to_a 可以换成 x.transpose 吧?

给定数组里带 nil 怎么办?


循环版:

i = 0
arr.group_by{ i+=1; i%n }.values

([arr.size / n] * (n - 1) << (arr.size / n + arr.size % n)).map { |i| a.shift(i) } ...

3# +1,尽量找多的,多了去掉就 OK 了

#3 楼 @luikore 恩,这个答案已经接近完美了,唯一遗憾的是还产生了一个局部变量 我的解法中 nil 的问题是个疏漏,不过我用到的场景中,nil 是不用考虑的

here:

a = [1, 2, 3, 4]
a.combination(1).to_a  #=> [[1],[2],[3],[4]]
a.combination(2).to_a  #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
a.combination(3).to_a  #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

我的生成的结果稍微整齐一点。虽然号称是最丑陋版。

def split_group(array, n)
  size = array.size
  div, mod = size.divmod(n)
  new_array = array.each_slice(div).to_a
  return new_array if mod == 0
  x, y = new_array.take(n), new_array.drop(n).flatten
  enum_x = x.cycle
  enum_y = y.to_enum
  loop { enum_x.next << enum_y.next }
  x
end

#6 楼 @fsword

何必太在意多出来一个或两个本地变量呢?你只要保证方法很小 (不超过 7 行), 并且只在方法内部使用本地变量就没问题呀。倒是问题在于:本地变量的命名,除了 x,y, 我实在是找不出好的名字,经常因为这个事情恼火。

说实话,我很佩服你动不动就一大长串,我反正是写不出来你那么长一串串的实现,头晕的要死。

数组应该是一个有序的集合,我觉得最有 (现实) 意义的实现应该是连续的元素才好。这又增加了实现难度。不妨把标题改一改继续呀。

#7 楼 @xds2000 这不是我要的结果啊 #8 楼 @zw963 我那可不是好代码,只是为了说明需求,我觉得 @luikore 的代码通常都很好

#9 楼 @zw963 这个倒不是必须的,我最近常遇到这类场景,一般是为了切分数据用于并行计算,比如多线程之类

@fsword 最近太忙了,实在没时间分析,求大虾出招啊

a= (1..8).to_a
#=> [1, 2, 3, 4, 5, 6, 7, 8]
b = []
n = 3   # 拆成n个
count = (a.size/n).ceil   # 每个子数组的元素)
count.times {|i| b << a[(i*count)...((i+1)*count)]}
b #=> [[1, 2, 3], [4, 5, 6], [7, 8]]

这样?貌似行数挺多……

#13 楼 @hegwin 有漏洞,你说的应该是这样吧

a = (1..8).to_a
n = 3
b = []
(a.size.to_f / n).ceil.times{|i| b << a[(i*n)...((i+1)*n)]}
b

但是这样不能满足要求,比如 a 的 size 为 18,n 为 5,数组会拆成4,4,4,4,2,而更平均的结果应该是4,4,4,3,3

@fsword 这样子吧,我还是喜欢思路简单的 我们设定个场景,分球到盒子里,要最平均的话,就是说轮流挨个往里放,这是基本想法。 但是这样顺序就变了(我有也不太明白顺寻变了好不好),不如计算下哪几个盒子放得多……

class Array
  def equal_divise n
    source = self.clone
    size = self.size.to_f
    result = []
    n.times {|i| result << (source.pop i>=size%n ? (size/n).ceil : (size/n).floor)}
    result.reverse
  end
end

我写在类里面了,如果不在乎顺序,可以把 reverse 之类去掉…… 不过还是觉得行数有点多啊,求简化……

a = ('A'..'Z').to_a
#=> 26个字母的数组
a.equal_divise 4
#=> [["A", "B", "C", "D", "E", "F", "G"], ["H", "I", "J", "K", "L", "M", "N"], ["O", "P", "Q", "R", "S", "T"], ["U", "V", "W", "X", "Y", "Z"]]
需要 登录 后方可回复, 如果你还没有账号请 注册新账号