discrete

组合数学中的组合幻影类型

变更日志

该库用于通过组合构建算法，该算法映射到自然数并从自然数返回。

例如，一对是一个元组 (a, b)，其中 b > a。它可以表示图中两个节点之间的无向边。

一对可以映射到自然数并从自然数返回。这可以用来存储和检索与边相关联的信息。

在该库中，一对表示为类型 Pair。当您需要所有成对的元组时，您可以写 Pair<Of<Pair>>。

为什么？

映射到自然数并从自然数返回的离散空间具有许多良好的数学属性。例如，它可以通过列出自然数直到一个限制来枚举所有可能的结构。

如果两个结构映射到自然数并从自然数返回直到相同的“计数”（在数学文献中通常称为“基数”），则这两个结构是等价的（同构的）。与其直接证明 A 和 B 之间的同构，不如证明 A ~=> nat 和 B ~=> nat，然后证明它们具有相同的基数。

原则上您可以使用数字，但编写正确的算法会非常困难。此库通过类型组合为您提供正确的算法。

离散空间的另一个应用是获得复杂性的上界。通过将更多关于问题的信息编码到离散空间中，可以得到复杂性的下限上界，并且通常同时学习一些新的对称性。一个有效的将问题编码到离散空间中的方法可以告诉您如何有效地解决问题。

离散空间也很容易相互组合。您可以创建一个，看看当它与其他空间组合时会发生什么。

如何在问题解决中使用离散空间

想象一下有4个人住在3个不同的房子里。有多少种组合方式，你能列出所有组合吗？

这种问题在现实生活中很常见。一个共同的特点是问题中包含大量的未知变量和不确定性。我们的大脑很难同时考虑许多可能性，但通过使用计算机，我们有时可以使用穷举法。

解决方案

3^4 = 81

// Each digit position represents a person and the value is where the person lives.
0000
0001
0002
0010
0011
0012
0020
...
3333

这种类型的离散空间可以通过类型 DimensionN 来构建。有4个维度，每个维度代表一个人，每个维度的大小为3。

离散空间可以解决自然语言模糊性的问题。

现在，考虑另一个问题

想象4对夫妇住在3个不同的房子里。一个房子里最多住2对夫妇，但没有任何房子是空的。有多少种组合方式，你能列出所有组合吗？

注意这个问题与第一个问题相似，其中人们被夫妇所取代，并增加了一个限制条件，使得一些组合无效。

一种方法是使用与第一个问题相同的算法，并过滤掉所有不符合约束条件的解决方案。每个数字代表一对夫妇而不是一个人。

另一种方法是使用8个人与相同的算法，然后只选择那些一个房子里包含两个或四个人的解决方案。

这两种解决方案都是有效的答案，但它们回答了不同的问题。第一种方法忽略了个体之间的排列，而第二种方法忽略了夫妇之间的排列。我们如何理解事物可能取决于我们使用的算法，但在非正式场合这可能会产生歧义。

离散空间是一种非歧义的表示所有可能性的方法，它从解空间的拓扑和维度出发。空间中的每个状态对应于一个单独的位置或更大问题的一个子结构。换句话说，自然数在编程中充当类似于泛型类型的占位符。

离散空间的结构并不能自动给出答案，但它一旦定义清楚，就更容易从每个角度检查问题。

这种方法的一个好处是，你可以从一个低维度开始，以确保你理解了问题，然后扩展到可能性空间的实际大小。例如，当存在用于计数可能性的数学公式时，离散空间用于测试公式中的前几个数字。

有时，大的解空间包含对称性，可以将其压缩到一个较小的空间。这有助于提高搜索和分析的性能。在解决问题时，你一开始可能没有意识到这些对称性，但你可以从一个一般的空间开始，然后添加对称性的假设来使空间变小。常用的一种技术是将问题分成对称部分和非对称部分，以便在更简单的情况下使用更有效的算法。