TDD 字符串组合练习
5.00/5 (5投票s)
一个关于测试驱动开发（TDD）字符串组合练习的实际示例
介绍
本文展示了我按照 www.cyber-dojo.com 上的描述，用 C# 实现的字符串组合练习。
Write a program to generate all potential anagrams of an input string.
For example, the potential anagrams of "biro" are
biro bior brio broi boir bori
ibro ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib
背景
Kata（练习）是一种刻意练习的形式。Katas 是程序员每天完成的小型编码练习。程序员不应该每天尝试一个新的 Kata，而应该反复练习同一个 Kata，直到完成 Kata 几乎成为一种本能。
这样做的好处包括：提高开发工具使用效率，更好地理解编程语言的特性，以及更好地掌握 TDD。
使用代码
附带的项目包含代码的最终版本。为了从本文中获益，你不应该直接跳到最终代码。尝试自己做这个练习，或者跟随我的步骤一起学习。
练习内容
让我们写一个测试。
[Test]
public void NoCharacters()
{
var expected = new List<string> {""};
Assert.That(Anagrams.Of(""), Is.EqualTo(expected));
} 几乎总是如此，我们从空字符串的退化情况开始。我们这样做不仅仅是为了确保退化情况得到处理（这是其中的一部分），而是通过第一个测试，我们正在考虑我们新代码的 API。
你可以看到，我们正在编写的函数将是 `Anagrams` 类中的一个静态方法，名为 `Of`，它允许我们以相对流畅的方式使用 `Anagrams.Of(s)`。这是简单的测试驱动设计，我们编写测试，就好像期望的代码已经存在一样，这理论上会给我们可能希望获得的最佳 API。
为了使该测试通过，我们需要一个类、一个方法，并返回一个满足测试的字面值。
public class Anagrams
{
public static List<string> Of(string s)
{
return new List<string> {""};
}
} 我们进入了 GREEN（绿色）状态。我们可能会 tempted（诱惑）地直接返回 `s` 然后结束。这样测试会通过，并且也能处理单个字符字符串的情况。考虑我们还没有写过的测试表明我们有些操之过急了。让我们为单个字符的例子写一个测试。
[Test]
public void OneCharacter()
{
var expected = new List<string> { "A" };
Assert.That(Anagrams.Of("A"), Is.EqualTo(expected));
} 现在我们有了一个失败的测试，让我们让它通过。如上所述，我们可以返回 `'s'`，这样我们的两个测试都会通过。采取这类步骤是可以的，如果一个测试意外失败，我们可以撤销更改，然后更慢地尝试。
为了练习的目的，我们现在慢慢来，看看一种稍后在情况更复杂时对我们很有帮助的技术。我们将隔离现有的工作代码，用代码中的一个分支来使新测试通过，然后尝试消除这个分支。下面是让两个测试都通过的方法。
public static List<string> Of(string s)
{
if(s == "")
return new List<string> {""};
return new List<string>{"A"};
} `if` 语句处理了空字符串的情况，所以我们的新代码不会破坏它。我们使用字面值 `"A"` 来尽可能简单地使新测试通过。这样就在测试中的字面值 `"A"` 和代码中相同的值之间产生了重复。我们可以通过概括单个字符的解决方案来消除这种重复，返回 `s` 是返回 `"A"` 的更通用的形式。
public static List<string> Of(string s)
{
if(s == "")
return new List<string> {""};
return new List<string>{s};
} 现在很清楚，返回 `s` 会使我们的两个测试都通过，所以让我们进行重构。
public static List<string> Of(string s)
{
return new List<string>{s};
} 又到了写测试的时间了。怎么处理两个字符的呢？
[Test]
public void TwoCharacters()
{
var expected = new List<string> { "AB", "BA" };
Assert.That(Anagrams.Of("AB"), Is.EqualTo(expected));
}让我们重复同样的技巧，用一个 `if` 语句来保护现有的工作代码，并使用最简单的实现来使测试通过。
public static List<string> Of(string s)
{
if(s.Length<=1)
return new List<string>{s};
return new List<string>
{
"AB",
"BA"
};
} 我们又回到了测试和代码之间的重复，让我们打破它。
public static List<string> Of(string s)
{
if(s.Length<=1)
return new List<string>{s};
return new List<string>
{
s,
s.Substring(1,1) + s.Substring(0,1)
};
} 这样可以处理 0 到 2 个字符的任何字符串。下一个测试，三个字符。
[Test]
public void ThreeCharacters()
{
var expected = new List<string> { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" };
Assert.That(Anagrams.Of("ABC"), Is.EqualTo(expected));
} 要让它通过？你现在应该知道流程了。隔离现有代码，并硬编码一个解决方案。
public static List<string> Of(string s)
{
if (s.Length <= 1)
return new List<string> { s };
if(s.Length == 2)
{
return new List<string>
{
s,
s.Substring(1,1) + s.Substring(0,1)
};
}
return new List<string>
{
"ABC",
"ACB",
"BAC",
"BCA",
"CAB",
"CBA"
};
}这里出现了一个模式。让我们把字符串分割开，让它更清晰。
return new List<string>
{
"A" + "BC",
"A" + "CB",
"B" + "AC",
"B" + "CA",
"C" + "AB",
"C" + "BA"
};我们可以替换每一行的第一个字符。
return new List<string>
{
s.Substring(0,1) + "BC",
s.Substring(0,1) + "CB",
s.Substring(1,1) + "AC",
s.Substring(1,1) + "CA",
s.Substring(2,1) + "AB",
s.Substring(2,1) + "BA"
};这达到了什么目的？我们仍然在每一行都有字面值。是的，我们有，但它们看起来很熟悉。“BC”和“CB”看起来就像“BC”的组合。同样适用于“AC”、“CA”以及“AB”、“BA”。我们发现生成三个字符组合的一部分工作是生成两个字符的组合。让我们看看是否能让它更明确。
return new List<string>
{
s.Substring(0,1) + Anagrams.Of("BC")[0],
s.Substring(0,1) + Anagrams.Of("BC")[1],
s.Substring(1,1) + "AC",
s.Substring(1,1) + "CA",
s.Substring(2,1) + "AB",
s.Substring(2,1) + "BA"
}; 如果我们得到 `Anagrams.Of("BC")`，我们会得到两个结果。第一个是“BC”，第二个是“CB”。我们可以对剩余的字面值重复这个更改。
return new List<string>
{
s.Substring(0,1) + Anagrams.Of("BC")[0],
s.Substring(0,1) + Anagrams.Of("BC")[1],
s.Substring(1,1) + Anagrams.Of("AC")[0],
s.Substring(1,1) + Anagrams.Of("AC")[1],
s.Substring(2,1) + Anagrams.Of("AB")[0],
s.Substring(2,1) + Anagrams.Of("AB")[1]
};等等，我们所有 6 行仍然有字面值。我们有任何进展吗？还是我们只是在转移问题？我们已经取得了进展。我们实际上消除了大约一半的字面值。现在我们几乎可以完全删除这些字面值了。记住原始字符串 `s` 的值为“ABC”，所以为了得到前两行的“BC”，我们需要从“ABC”中去掉第一个字符（“A”）。
是时候做更多的 TDD 了，让我们假装我们有我们需要的功能。
return new List<string>
{
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[0],
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[1],
s.Substring(1,1) + Anagrams.Of("AC")[0],
s.Substring(1,1) + Anagrams.Of("AC")[1],
s.Substring(2,1) + Anagrams.Of("AB")[0],
s.Substring(2,1) + Anagrams.Of("AB")[1]
}; 这无法编译，因为我们没有 `DropCharacter` 函数。让我们用最简单的方法让测试通过。
private static string DropCharacter(string s, int index)
{
return "BC";
} 严格来说，我跳过了一个步骤。我实际上会创建一个函数，让一切都能编译，但让它返回错误的值，这样我就有一个失败的测试。然后通过让函数返回“BC”让测试变为 Green。这让我确信我们的测试确实与代码连接在一起。
我们仍然在测试和代码之间存在字面值重复，但让我们先把 `DropCharacter` 函数完全弄好，然后再解决这个问题。现在，如果我们想删除第一个字符（“A”），它就可以工作。让我们尝试扩展它的使用。
return new List<string>
{
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[0],
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[1],
s.Substring(1,1) + Anagrams.Of(DropCharacter(s,1))[0],
s.Substring(1,1) + Anagrams.Of(DropCharacter(s,1))[1],
s.Substring(2,1) + Anagrams.Of("AB")[0],
s.Substring(2,1) + Anagrams.Of("AB")[1]
}; 这将导致一个失败的测试。下一个失败的测试不一定非得是一个新测试。我们实际上已经有了所有需要的测试。这里发生的是，我们试图让我们的代码的一部分变得更通用，在此过程中，我们发现了代码中其他地方的硬编码问题。我们有效地通过代理测试驱动着 `DropCharacter` 函数。我们的 `Anagrams.Of` 函数以它无法处理的方式使用了 `DropCharacter`。
你应该已经知道如何回到 Green（绿色）状态了，用一个 `if` 来保护工作代码，并尽可能简单地使新测试通过。
private static string DropCharacter(string s, int index)
{
if(index == 0)
return "BC";
return "AC";
} 让我们处理完 `DropCharacter` 的最后一种情况，然后看看我们的进展。
return new List<string>
{
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[0],
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[1],
s.Substring(1,1) + Anagrams.Of(DropCharacter(s,1))[0],
s.Substring(1,1) + Anagrams.Of(DropCharacter(s,1))[1],
s.Substring(2,1) + Anagrams.Of(DropCharacter(s,2))[0],
s.Substring(2,1) + Anagrams.Of(DropCharacter(s,2))[1]
};为了让这个通过，我们将使用另一个 `if`。
private static string DropCharacter(string s, int index)
{
if(index == 0)
return "BC";
if(index == 1)
return "AC";
return "AB";
}是时候进行一些重构了。我们需要彻底消除这些字面值。删除第一个和最后一个字符很容易。
private static string DropCharacter(string s, int index)
{
if(index == 0)
return s.Substring(1,2);
if(index == 1)
return "AC";
return s.Substring(0,2);
}
我们硬编码了 `Substring` 的参数，这意味着我们仍然依赖于三个字符的字符串。一步一步来。让我们处理删除中间字符的情况，然后看看是否可以将其推广到任何字符串长度。
if(index == 1)
return "A" + "C";字母“B”被删除了，“A”和“C”代表删除字母之前和之后的部分字符串。所以，我们分割字符串并分别处理每一部分。
if(index == 1)
return s.Substring(0,1) + s.Substring(2,1);这是我们的现状。
private static string DropCharacter(string s, int index)
{
if(index == 0)
return s.Substring(1,2);
if(index == 1)
return s.Substring(0,1) + s.Substring(2,1);
return s.Substring(0,2);
}我们消除了对字面字符串的依赖，但取而代之的是对特定长度字符串的依赖。这在某种程度上是进步。我们有字符串 `s` 和要处理的删除字符的 `index`。我们需要将这些硬编码值追溯到这两个输入。这可能有点棘手。
让我们先从删除字符之前的部分字符串开始。函数中有两个地方引用了这部分字符串，通过使用 `index` 变量，我们可以消除一些字符数量的硬编码。
private static string DropCharacter(string s, int index)
{
if(index == 0)
return s.Substring(1,2);
if(index == 1)
return s.Substring(0,index) + s.Substring(2,1);
return s.Substring(0,index);
}我们可以引入一个 `before` 变量来明确这一点。
private static string DropCharacter(string s, int index)
{
var before = s.Substring(0, index);
if (index == 0)
return s.Substring(1,2);
if(index == 1)
return before + s.Substring(2,1);
return before;
}现在我们需要处理删除字符之后的那部分字符串。代码中又有两个这样的例子。我们可以看到 `Substring` 的第一个参数，即子字符串的起始位置似乎是 `index + 1`。我们把它插进去。
private static string DropCharacter(string s, int index)
{
var before = s.Substring(0, index);
if (index == 0)
return s.Substring(index + 1, 2);
if(index == 1)
return before + s.Substring(index + 1, 1);
return before;
}`Substring` 的第二个参数并不那么简单，它取决于删除字符的索引和原始字符串的长度。尽管如此，它还是相对容易弄清楚的。
private static string DropCharacter(string s, int index)
{
var before = s.Substring(0, index);
if (index == 0)
return s.Substring(index + 1, s.Length - (index + 1));
if(index == 1)
return before + s.Substring(index + 1, s.Length - (index + 1));
return before;
} 为了清晰起见，让我们引入另一个变量来真正使这一切都显而易见。
private static string DropCharacter(string s, int index)
{
var before = s.Substring(0, index);
var after = s.Substring(index + 1, s.Length - (index+1));
if (index == 0)
return after;
if(index == 1)
return before + after;
return before;
} 而且，我们可以像这样简化它。
private static string DropCharacter(string s, int index)
{
var before = s.Substring(0, index);
var after = s.Substring(index + 1, s.Length - (index+1));
return before + after;
} 我们的最后一个任务是将注意力转回到 `Anagrams.Of` 函数并解决它。
public static List<string> Of(string s)
{
if (s.Length <= 1)
return new List<string> { s };
if(s.Length == 2)
{
return new List<string>
{
s,
s.Substring(1,1) + s.Substring(0,1)
};
}
return new List<string>
{
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[0],
s.Substring(0,1) + Anagrams.Of(DropCharacter(s,0))[1],
s.Substring(1,1) + Anagrams.Of(DropCharacter(s,1))[0],
s.Substring(1,1) + Anagrams.Of(DropCharacter(s,1))[1],
s.Substring(2,1) + Anagrams.Of(DropCharacter(s,2))[0],
s.Substring(2,1) + Anagrams.Of(DropCharacter(s,2))[1]
};
} 创建三个字符单词的六个组合的那六行代码看起来很有希望。那里有一个相当明显的循环。
我们需要做的第一件事是删除列表初始化的代码，以便我们可以使用循环向列表中添加项。
var anagrams = new List<string>();
anagrams.Add(s.Substring(0, 1) + Anagrams.Of(DropCharacter(s, 0))[0]);
anagrams.Add(s.Substring(0, 1) + Anagrams.Of(DropCharacter(s, 0))[1]);
anagrams.Add(s.Substring(1, 1) + Anagrams.Of(DropCharacter(s, 1))[0]);
anagrams.Add(s.Substring(1, 1) + Anagrams.Of(DropCharacter(s, 1))[1]);
anagrams.Add(s.Substring(2, 1) + Anagrams.Of(DropCharacter(s, 2))[0]);
anagrams.Add(s.Substring(2, 1) + Anagrams.Of(DropCharacter(s, 2))[1]);
return anagrams;现在让我们让一个循环起作用，并删除一些代码。
var anagrams = new List<string>();
for (int i = 0; i < 3; i++ )
{
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[0]);
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[1]);
}
return anagrams;我们可以嵌套另一个循环以进一步减少代码量。
for (int i = 0; i < 3; i++ )
for (var j = 0; j < 2; j++)
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[j]);
两个循环的上界都是硬编码的。让我们删除它们。
for (int i = 0; i < s.Length; i++ )
for (var j = 0; j < s.Length - 1; j++)
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[j]);
花了很长时间才到这里，但现在我们可以清理 `Anagrams.Of` 函数了。
public static List<string> Of(string s)
{
if (s.Length <= 1)
return new List<string> { s };
var anagrams = new List<string>();
for (var i = 0; i < s.Length; i++ )
for (var j = 0; j < s.Length - 1; j++)
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[j]);
return anagrams;
}就 Kata 而言，我们也许可以称之为完成，毕竟目标更多的是关于工具和流程，而不是最终代码。但有一个大问题。我们的最终代码是错误的。
我们引入了一个 bug。我们在“小心”的循序渐进的代码细化过程中搞砸了。
我们将 `Anagrams` 函数测试到了长度为 3 的字符串。我们正处于为更长字符串创建测试变得痛苦的地步，仅仅是因为预期结果列表的巨大规模。但是，如果我们尝试运行更长的字符串，即使是 4 个字符的字符串，它也会给出不正确的结果。
我们可以在不列出所有预期结果的情况下证明这一点。尝试以下测试：
[Test]
public void CountOfAnagramsOfFourCharacters()
{
Assert.That(Anagrams.Of("ABCD").Count, Is.EqualTo(24));
} 我们知道答案应该是 24，因为结果的数量应该是原始字符串长度的阶乘。如果你还不知道，现在你就知道了。严格来说，整篇文章都是关于排列，而不是字符串组合。
无论如何，回到测试。它会失败。而不是我们预期的 24 个结果，我们得到了 12 个。为什么？怎么会发生这种事？
好吧，还记得我说过替换字面值可能会很棘手吗？在这种情况下，我们被这个问题咬了。我们做了一个假设，而这个假设误导了我们。
我们的嵌套循环最初是这样的：
for (int i = 0; i < 3; i++)
for (var j = 0; j < 2; j++)
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[j]); 我们通过细化到如下代码消除了循环保护中的字面值：
for (int i = 0; i < s.Length; i++)
for (var j = 0; j < s.Length - 1; j++)
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[j]);
外部循环中的 3 被字符串的长度替换，这是正确的，因为我们正在迭代字符串中的字符。
那么内部循环中的 `j<2` 呢？
2 是 3-1，对吗？
`j < s.Length - 1`?
我们达到了 Green（绿色），任务完成？
除了我们还没完成。这是一种巧合通过的情况。这是当我们盲目重构代码而不真正思考正在发生的事情时的情况。
内部循环迭代的是在删除字符后剩余字符的所有组合。对于一个三个字符的字符串，我们剩下 2 个字符，而任何两个字符的字符串都有 2 个组合。我们把我们的 2 弄混了。
我们应该这样做，而不是上面的代码：
public static List<string> Of(string s)
{
if (s.Length <= 1)
return new List<string> { s };
var anagrams = new List<string>();
for (var i = 0; i < s.Length; i++)
for (var j = 0; j < Anagrams.Of(DropCharacter(s, i)).Count; j++)
anagrams.Add(s.Substring(i, 1) + Anagrams.Of(DropCharacter(s, i))[j]);
return anagrams;
}
这修复了 bug，但它很丑陋，而且效率低下。
但是，我们现在是合法地达到了 Green（绿色），所以我们可以有信心地进行重构。
for (var i = 0; i < s.Length; i++)
{
var anagramsOfRest = Anagrams.Of(DropCharacter(s, i));
for (var j = 0; j < anagramsOfRest.Count; j++)
anagrams.Add(s.Substring(i, 1) + anagramsOfRest[j]);
} 我们可以再调整一下。
for (var i = 0; i < s.Length; i++)
{
var anagramsOfRest = Anagrams.Of(DropCharacter(s, i));
foreach (var anagramOfRest in anagramsOfRest)
anagrams.Add(s.Substring(i, 1) + anagramOfRest);
} 再调整一下。
for (var i = 0; i < s.Length; i++)
{
var droppedCharacter = s.Substring(i, 1);
var anagramsOfRest = Anagrams.Of(DropCharacter(s, i));
foreach (var anagramOfRest in anagramsOfRest)
anagrams.Add(droppedCharacter + anagramOfRest);
} 就这样。这是测试和代码的完整列表。
namespace AnagramKata
{
[TestFixture]
public class AnagramTests
{
[Test]
public void NoCharacters()
{
var expected = new List<string> { "" };
Assert.That(Anagrams.Of(""), Is.EqualTo(expected));
}
[Test]
public void OneCharacter()
{
var expected = new List<string> { "A" };
Assert.That(Anagrams.Of("A"), Is.EqualTo(expected));
}
[Test]
public void TwoCharacters()
{
var expected = new List<string> { "AB", "BA" };
Assert.That(Anagrams.Of("AB"), Is.EqualTo(expected));
}
[Test]
public void ThreeCharacters()
{
var expected = new List<string> { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" };
Assert.That(Anagrams.Of("ABC"), Is.EqualTo(expected));
}
[Test]
public void CountOfAnagramsOfFourCharacters()
{
Assert.That(Anagrams.Of("ABCD").Count, Is.EqualTo(24));
}
}
public class Anagrams
{
public static List<string> Of(string s)
{
if (s.Length <= 1)
return new List<string> { s };
var anagrams = new List<string>();
for (var i = 0; i < s.Length; i++)
{
var droppedCharacter = s.Substring(i, 1);
var anagramsOfRest = Anagrams.Of(DropCharacter(s, i));
foreach (var anagramOfRest in anagramsOfRest)
anagrams.Add(droppedCharacter + anagramOfRest);
}
return anagrams;
}
private static string DropCharacter(string s, int index)
{
return s.Substring(0, index) + s.Substring(index + 1, s.Length - (index + 1));
}
}
}结论
在这篇文章中，我们讨论了 Kata 作为刻意练习的手段的概念。我们已经看到了功能如何能够由测试驱动，逐步添加。我们也看到了如何在使新测试通过的最简单方法的同时保护现有代码，以及如何然后泛化这些简单的具体解决方案以消除重复。
最后，我们超越了 Kata，探讨了即使在使用 TDD 时，bug 如何被引入和错过，以及我们应该如何使用失败的测试来隔离 bug，然后修复 bug，使所有测试都通过。