如何让Ruby代码更简练？!（原文最终修订于 2006-08-18 下午02：42：25）

你可以用它来做什么呢？请阅读...

我四前年曾接触过Ruby，就是为了看看这个语言到底什么样。我用了它一段时间然后就把注意力放到Fit，Fitness（译注1），和Java/.Net上了。然而最近，随着Rails的兴起，我又开始关注Ruby了；也开始认识到这是一个多么高效、亲和的语言。

学习一项事物最有效的还是通过实战学习。所以我决定从一个Ruby的Kata（译注2）开始，这样就可以反复去练习。我从Laurent Bossavit（译注3）的blog里挑出了哈利波特的Kata一篇。要解决这个问题中的某一块，就涉及到一种能产生一个集合的所有可能组合的算法。我在类库中寻找能做这种组合算法的模块，但只发现了一个做排列的家伙。所以我决定自己写一个。我觉得先写一个组合迭代器的测试会比较有趣。

这里就是使用rspec来写的测试：

require 'spec'
require 'Combinations'

context "Simple Combinations" do
specify "degenerate cases" do
Combinations.get(0,0).should.equal []
Combinations.get(1,0).should.equal []
Combinations.get(0,1).should.equal []
end

specify "nC1" do
Combinations.get(1,1).should.equal [[0]]
Combinations.get(2,1).should.equal [[0],[1]]
end

specify "nCn" do
Combinations.get(2,2).should.equal [[0,1]]
Combinations.get(3,3).should.equal [[0,1,2]]
end

specify "nCr" do
Combinations.get(3,2).should.equal [[0,1],[0,2],[1,2]]
Combinations.get(4,3).should.equal [[0,1,2],[0,1,3],[0,2,3],[1,2,3]]
Combinations.get(5,3).should.equal [
[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],
[1,2,3],[1,2,4],[1,3,4],
[2,3,4]

]
end

end

而这里就是那些通过测试的组合模块：

class Combinations
  def self.c(n,r,&proc)
    if (n>0 && r>0)
      combine([], 0, n, r, proc)
    end
  end

  def self.get(n,r) 
    combinations = []
    Combinations.c(n,r) {|c| combinations << c}
    combinations
  end

  private
  def self.combine(combination, s, n, r, proc)
    if (r == 0)
      proc.call(combination)
    else
      (s..(n-r)).each {|i| combine(combination + [i], i+1, n, r-1, proc)}
    end
  end
end

我非常确定这个算法正确且有效。可是，我赫然发现一个稍早的版本固然精确，但效率却出奇的低。不同点在于：

(s...n).each {|i| combine(combination + [i], i+1, n, r-1, proc)}

令我烦心是，测试并没有发现这个效率低下的问题。我是在之后所做的一些手工的探索测试中才发现了这点。我想应该把它放在一个单元测试中来确保一个特定的最低效率值。不过我会把它放在另一篇blog中。

这篇blog的真正主题

是我不喜欢这个代码，它太不清晰了。可是到目前为止我还没找到一种让它更好的办法。我的目标是找到一种展现代码的方式，这样这个算法就能以明朗的面貌展现出来。我的这个算法太拥挤了，而且不能把自己描述清楚。（如何判断拥挤指数呢？就是让你完全理解它在做什么和为什么它能通过测试所花的时间的多少。）

有什么建议吗？

译者的话：因本文秉承Uncle Bob一贯的集思广益风格，属于一篇探讨性blog。原blog中有大量的专家讨论，译者特还其以原貌（请见以下评论内容），让大陆友人能够汲取更多相关知识。

----------------------------------------------------------------------------------------------------------

评论之一：

来自-> Matteo Vaccari

题目-> 清理组合代码

这些事情最好用递归定义的方式来解决。
让函数choose(n, k)来找出来自集合(0...n)的k个元素的所有不同组合。那么
choose(3, 0) == [[]]
choose(3, 1) == [[0], [1], [2]]
choose(3, 2) == [[0,1], [0,2], [1,2]]
等等。我们也有
choose(3, 4) == []
因为没办法从仅仅三个元素中找出4种元素的不同组合。
所以，让我们给choose(n, k)来写一个递归的定义；基本的情况是
choose(0, 0) == [[]]
choose(0, k) == [] if k > 0
这覆盖了所有n == 0 时的情况。现在让我们看看n==3，
choose(3, 1) == [[0], [1], [2]]
choose(3, 2) == [[0,1], [0,2], [1,2]]
那当n==4时会怎样呢？
choose(4, 2) == [[0,1], [0,2], [1,2], [0,3], [1,3], [2,3]]
酷！看起来前面一半和choose(3,2)一样
choose(4, 2) == choose(3, 2) + [[0,3], [1,3], [2,3]]
剩下的元素与choose(3,1)再加上新元素3是一样的

choose(4, 2) == choose(3, 2) + append_all(choose(3,1), 3)
这就说明这是一个普遍的规则。从一组(n+1)个元素元素中选出不同的k个元素的所有组合的方式是：
- 从一组n个元素中选出k个元素的所有组合，再加上
- k-1个旧元素的所有组合加上一个新的元素

测试优先!

def test_base
assert_equal [[]], choose(3, 0)
assert_equal [], choose(0, 3)
end

def test_step
# choose(1,1) == choose(0, 1) + append_all(choose(0, 0), 0)
# == [] + append_all([[]], 0)
# == [[0]]
assert_equal [[0]], choose(1, 1)
assert_equal [[0,1], [0,2], [1,2]], choose(3, 2)
assert_equal [[0,1], [0,2], [1,2], [0,3], [1,3], [2,3]], choose(4, 2)
assert_equal [[0,1,2,3]], choose(4, 4)
end

通过测试的代码是

def choose(n, k)
return [[]] if n == 0 && k == 0
return [] if n == 0 && k > 0
return [[]] if n > 0 && k == 0
new_element = n-1
choose(n-1, k) + append_all(choose(n-1, k-1), new_element)
end

def append_all(lists, element)
lists.map { |l| l << element }
end
既然我们递归调用k-1,我们必须增加一段代码去定义当k==0时的情况。这段代码当然是精简的。它也是清晰的，只要你明白了递归定义是如何

奏效的。

评论之二：

来自-> Dean Wampler

题目-> 一个更“美化”的调整？

这里是一个原始的rspec测试的调整，它试图用更美化的方式来封装Combinations.get()的调用，使用一个全局方法：

require 'spec'
require 'Combinations'

def get_combinations args
Combinations.get args[:for_n_items], args[:sets_of]
end

context "Simple Combinations" do
specify "degenerate cases" do
get_combinations(:sets_of => 0, :for_n_items => 0).should.equal []
get_combinations(:sets_of => 0, :for_n_items => 1).should.equal []
get_combinations(:sets_of => 1, :for_n_items => 0).should.equal []
end

specify "nC1" do
get_combinations(:sets_of => 1, :for_n_items => 1).should.equal [[0]]
get_combinations(:sets_of => 1, :for_n_items => 2).should.equal [[0],[1]]
end

specify "nCn" do
get_combinations(:sets_of => 2, :for_n_items => 2).should.equal [[0,1]]
get_combinations(:sets_of => 3, :for_n_items => 3).should.equal [[0,1,2]]
end

specify "nCr" do
get_combinations(:sets_of => 2, :for_n_items => 3).should.equal [[0,1],[0,2],[1,2]]
get_combinations(:sets_of => 3, :for_n_items => 4).should.equal [[0,1,2],[0,1,3],[0,2,3],[1,2,3]]
get_combinations(:sets_of => 3, :for_n_items => 5).should.equal [
[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],
[1,2,3],[1,2,4],[1,3,4],
[2,3,4]

]
end

end

如果经常用的化会显得有些冗长，可是这对第一次使用的读者来说可以更容易读懂，而且也是个选择。

----------------------------------------------------------------------------------------------------------

译注：

1，Fit，Fitness，一个Object Mentor公司开发的关于验收性测试的知名框架，详情可访问http://fitnesse.org/。

2，Kata，是目前北美和欧洲一些领先的软件咨询公司开创的一种用于掌握软件开发技能的手段，类似于国人乐谈的武功招式。目的就是试图寻找出软件开发中的一些招式，让学习者可以不断演练，从而打下一个良好的基础。

3，Laurent Bossavit，敏捷领域的一位知名专家，并有热门blog。

（原文链接网址：http://www.butunclebob.com/ArticleS.UncleBob.RubyCombinations;

Robert C. Martin的英文blog网址：http://www.butunclebob.com/ArticleS.UncleBob）

译者注：Robert C. Martin是Object Mentor公司总裁，面向对象设计、模式、UML、敏捷方法学和极限编程领域内的资深顾问。他不仅是Jolt获奖图书《敏捷软件开发：原则、模式与实践》（中文版）（《敏捷软件开发》（英文影印版））的作者，还是畅销书Designing Object-Oriented C++ Applications Using the Booch Method的作者。Martin是Pattern Languages of Program Design 3和More C++ Gems的主编，并与James Newkirk合著了XP in Practice。他是国际程序员大会上著名的发言人，并在C++ Report杂志担任过4年的编辑。