用Lingo解决组合问题
|
|
|
|
作者：佚名
来源：InterNet 加入时间：2005-2-7 |
|
[问题]
有5张卡片，从中任取3张，列出所有可能的结果。
[分析]
输入卡片列表并确定最终组合列表的长度 ——〉计算组合的总数并生成组合列表 ——〉输出组合列表
[代码]
由于是有关排列组合的问题，必然会涉及到阶乘的计算。为了方便起见，可以先设计一个阶乘计算程序：
on mGetFactorial (me, num)
factorial = 1
repeat with x = num down to 1
factorial = factorial * x
end repeat
return factorial
end
接下来，就可以利用这个阶乘计算程序得到组合的总数：
-- 计算阶乘
listFactorial = me.mGetFactorial(pListCount)
subsetFactorial = me.mGetFactorial(pSubsetCount)
listMinusSubsetFactorial = me.mGetFactorial(pListCount - pSubsetCount)
-- 计算组合总数
pTotal = listFactorial / (subsetFactorial * (listMinusSubsetFactorial))
pNumLeft = pTotal
现在，借助一个索引数值，通过循环语句即可生成一个索引列表：
on mGetCombination (me)
-- 检测是否为第一次循环
if pNumLeft = pTotal then
-- 是第一次循环，使用当前子列表
pNumLeft = pNumLeft - 1
else
-- 不是第一次循环，获取新的子列表
x = pSubsetCount
-- 在当前子列表中循环并增值
repeat while pCurrentSubset[x] = pListCount - pSubsetCount + x
x = x - 1
end repeat
pCurrentSubset[x] = pCurrentSubset[x] + 1
repeat with y = (x + 1) to pSubsetCount
pCurrentSubset[y] = pCurrentSubset[x] + y - x
end repeat
-- 获取新的子列表
pNumLeft = pNumLeft - 1
end if
end
之所以没有直接对实际的卡片列表进行直接操作，是为了让程序拥有更强的适应性。因为只要拥有了索引列表，就可以对任何传入的实际列表进行“组合”操作，而不仅仅限于这个卡片列表。当然，只需再添加一些代码，即可生成实际的结果列表：
-- 生成结果列表
combination = []
repeat with x = 1 to pSubsetCount
combination.add (pItemList[pCurrentSubset[x]])
end repeat
[说明]
这项技巧虽然比较简单，但使用的范围却非常广泛，例如卡片的随机抽取或数列的随机生成。此外，在许多涉及到需要列举组合结果的数学问题中都占有一席之地。
[文章录入员:nancy] |
|
|
|
|
