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

quakewang · 2012年02月29日 · 最后由 zw963 回复于 2012年03月01日 · 8871 次阅读

``````rand_split(array, max_element)
end
``````

``````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. 有单元测试更好 :)

``````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
``````
``````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
``````

``````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
``````

``````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
``````

``````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
``````

``````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
``````

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

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

``````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
``````

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 卡死

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

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

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

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

#16 楼 @quakewang 过分理解了题意：）

``````random_element = rand(max_element+1)
``````

``````result << copy.pop(random_element) until 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)}
``````

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

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

fredwu 提及了此话题。 04月03日 10:56