用Lingo解决组合问题

五星上将

[问题]

　　有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

　　下面的影片便是完成后的“组合生成器”：

　　[说明]

　　这项技巧虽然比较简单，但使用的范围却非常广泛，例如卡片的随机抽取或数列的随机生成。此外，在许多涉及到需要列举组合结果的数学问题中都占有一席之地。

gxj000

谢谢楼主提供分享！！

yipingzi

阳春白雪，逛一逛，看一看，顶一顶。