使用F#的排列与组合 - 面向对象网 f# 学习 对象 - 面向对象技术开发

面向对象技术开发

会员投稿 投稿指南 站长资讯通告:
您的位置: 首页 > OOP语言 > F# > 正文

使用F#的排列与组合

来源: www.bianceng.cn 阅读:

理解排列与组合是进行软件测试所需的一项基本技能。在本月的“测试运行”专栏中,我将向您展示如何使用以新 F# 语言编写的代码来处理排列与组合。

数学组合是指从包含 n 项的集合中选择 k 项作为子集,不考虑其中的顺序。例如,如果 n = 5 且 k = 2,需要从五项中选择二项,则所有可能的组合为:

{0,1}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

请注意,我没有列出组合 {1,0},这是因为它与 {0,1} 被视为相同的组合。另外,我使用的是一种称为字典编辑顺序的顺序列出这 10 个一次性五选二的组合。根据这种顺序,每个组合元素中的所有值以递增顺序列出。

数学排列是指对 n 项进行所有可能的排列。例如,如果 n = 4,以字典编辑顺序列出的所有可能的排列为:

{0,1,2,3}, {0,1,3,2}, {0,2,1,3}, {0,2,3,1}, {0,3,1,2}, {0,3,2,1}, {1,0,2,3}, {1,0,3,2}, {1,2,0,3}, {1,2,3,0}, {1,3,0,2}, {1,3,2,0}, {2,0,1,3}, {2,0,3,1}, {2,1,0,3}, {2,1,3,0}, {2,3,0,1}, {2,3,1,0}, {3,0,1,2}, {3,0,2,1}, {3,1,0,2}, {3,1,2,0}, {3,2,0,1}, {3,2,1,0}

在处理排列与组合时,有两个重要的函数:Choose(n,k) 和 Factorial(n)。您可能熟悉 Factorial(n) 函数,该函数通常缩写为 n!。Factorial(n) 函数返回 n 阶排列的元素总数。例如:

4! = 4 * 3 * 2 * 1 = 24.

Choose(n,k) 函数返回 n 选 k 组合的总数。

Choose(n,k) = n! / (k! * (n-k)!)

例如,

Choose(5,2) = 5! / (2! * (5-2)!) = 5! / (2! * 3!) = 120 / 12 = 10.

排列与组合是“组合数学”(或简称“组合学”)的研究范畴。

为了您了解我在本月专栏中要谈的问题,最好先看一下图 1 所示的屏幕截图。我使用了 Windows PowerShell 来承载我的 F# 演示应用程序,但也可以只简单地使用命令 Shell。我修改了 Windows PowerShell 启动脚本,以便能自动导航到我的 CombinatoricsDemo.exe 程序所在的位置。

\

图 1 使用 F# 的排列与组合

Tags:
相关文章列表: