算法 [Ruby Quiz] 将一个数组随机分割成N个元素的组合

quakewang · 发布于 2012年2月29日 · 最后由 zw963 回复于 2012年3月01日 · 6483 次阅读
162

以前翻译过一些ruby quiz,自己也出过一些ruby quiz: http://quake.iteye.com/blog/search?query=quiz 但是效果不太好,看看在Ruby China有没有人对这个感兴趣的

先出个小题目试试看,实现一个rand_split的方法,将一个数组随机分割成N个元素的组合

rand_split(array, max_element)
end

将0到10,随机分割成最大不超过3个元素的组合,输出结果可能是这样:

p rand_split (0..10).to_a, 3
=> [[0], [1,2], [3, 4, 5], [6, 7], [8], [9, 10]]

要求:

  1. 实现要简洁明了
  2. 性能不能太差
  3. ruby 1.8/1.9的语法都可以
  4. 有单元测试更好 :)

备注: array不需要shuffle,为了除去不必要的array.clone等代码干扰,可直接对array做改变。

共收到 21 条回复
78

没考虑性能和更高的随机性,只适应于数组小于10万元素的简单场合:

def rand_split(array, max_element)
  copy = array.shuffle
  result = []
  while copy.size > 0
    result << copy.slice!(0, rand(max_element) + 1)
  end

  result
end
96
def rand_split(array, max_element)
  list = []
  l = Array.new(array)
  list << (l.pop Random.rand(1..max_element) )  while l.count > 0 
  list
end
96

又写了一个,感觉效率应该好点,代码量长点

def hhuai_rand_split1(array, max_element)
  last = max_element
  total = last
  ll = []
  ss = 1..max_element
  while last > 0
    n =  Random.rand(ss)
    ll<<array[total-last,n]
    last -= n
  end
  ll
end
96

这是目前为止的benchmark, 1_000_000.times mac lion cpu i5 2.3 - ram 4g user system total real ashchan 5.100000 0.000000 5.100000 ( 5.102993) hhuai 6.640000 0.010000 6.650000 ( 6.639527) hhuai1 4.500000 0.000000 4.500000 ( 4.508758)

243
def test_rand_split
  array = (0..20).to_a
  max_element = 3
  rand_array = rand_split(array, max_element)
  p(rand_array.flatten == array)
  p(rand_array.select do 
    |array| not (1..max_element).to_a.include?(array.size)
  end.empty?)
end

提供一个测试, 自己的解题方法跟hhuai1类似.

1031

我把一楼的代码重写了下, 看起来更优雅, 更Rubyful

我简直爱死until和unless这种Ruby风格了, 我觉得只有 真的理解了这两个语句的内涵, 才算懂Ruby.

def rand_split(array, max_element)
  copy = array.shuffle
  result = []
  until copy.empty?
    random_element = rand(max_element+1)
    result << copy.pop(random_element)
  end
  result
end
1031

我之前的代码是这样写的.

def rand_split(array, max_element)
  copy = array.shuffle
  result = []
  random_element = rand(max_element + 1)
  result << copy.pop(random_element) until copy.nil?
  result
end

我承认这个代码逻辑有问题(没有吧生成随机数的代码包含在循环中) 可是我很郁闷的是, 为什么以上代码间歇性卡死?难道是使用pop的缘故吗? 隐约记得, 数组从左边越界, 好像会发生异常?

劳烦楼上几位帮忙分析下.

1031

刚才step调试了下, 问题就出在下面的语句:

result << copy.pop(random_element) until copy.empty?

随机性的出现卡死. 到底为什么

1031

@hhuai, Random.rand到底哪来的? 怎么我在1.86, 1.87, 1.92下面测试, 都不 可用呢? 也没那个库可以require啊.

713

因为你的 random_element可以等于0吧,是0copy.nil?不会到true

188
def rand_split(array, max_element=3)
  new_array = []

  while array != []
    new_array << array.shift(1 + rand(max_element))
  end

  new_array
end

MiniTest测试代码:

describe '#rand_split' do
  let(:array)  { (0..100).to_a }
  let(:result) { rand_split(array.clone, 3) }

  it 'returns an array of elements' do
    result.must_be_kind_of Array
    result[0].must_be_kind_of Array
  end

  it 'has a maximum of 3 items in each element' do
    result.each do |element|
      element.size.to_s.must_match /1|2|3/
    end
  end

  it 'has the correct number of total items' do
    result.flatten.size.must_equal array.size
  end

  it 'has elements containing 1 item' do
    result.sort{ |x, y| x.size <=> y.size }[0].size.must_equal 1
  end

  it 'does not have elements with more than 3 item' do
    result.sort{ |x, y| x.size <=> y.size }[-1].size.must_equal 3
  end
end
96

user system total real @fredwu 6.550000 0.000000 6.550000 ( 6.553984) hhuai1 4.580000 0.000000 4.580000 ( 4.575098) @ashchan 5.190000 0.010000 5.200000 ( 5.196660) hhuai 6.100000 0.000000 6.100000 ( 6.106076) zw963 卡死

这是最新的benchmark。

@zw963 这一句是死循环,永远为真。 result << copy.pop(random_element) until copy.nil?

913

数组需要 shuffle 么?

@ashchan@fredwu 的算法是等价的,@hhuai 的不一样(不会有类似 [[2], [10, 9, 6], [4, 5], [3, 8], [1, 7]] 这样的输出)

162

#15楼 @forresty 数组不需要shuffle,为了除去不必要的array.clone代码干扰,原始array也可以直接改变。

96

#15楼 @forresty 题目没说要洗牌,只说了要随机分组。

78

#16楼 @quakewang 过分理解了题意:)

1031

谢谢@azhao, @hhui, 问题已查清, 自己太粗心了, 需要深刻检讨!!!

不过首先说明下: 我也不知怎么搞的, 8楼的代码粘帖的时候搞错了, 应该 把nil?改为empty?.

问题出在下面这个句子上.

random_element = rand(max_element+1)

当random_element等于0时, copy.pop(0)总是弹出空的数组[], 下面的语句

result << copy.pop(random_element) until copy.empty?

成了无限循环, 因为没有任何元素真正从数组内弹出, copy.empty?总是为假.

下面是修改后的版本. 效率应该近似于一楼.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def rand_split(array, max_element)
  copy = array.shuffle
  result = []
  unless copy.empty?
    random_element = rand(max_element + 1) + 1
    result << copy.pop(random_element)
  end
  result
end

10000.times {p rand_split(a, 2)}
78

#19楼 @zw963 你这个解法好象是不正确的。你只取了一次随机数,所以分出来的数组大小都是相等的(除了最后一个)。另外 random_element = rand(max_element + 1) + 1会取到大于max_element的个数。

1031

@ashchan , 实在是晕. 哈哈 考虑了这个忘记了那个. 已经更改.

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