请教 关于组合数学的基本问题?
代码见 http://www.math.umn.edu/~stanton/5703/Subsets.p
现转载部分如下:
program Subsets (Input, Output);
const
MaxSetSize = 10;
type
Subset = array[0..MaxSetSize] of integer; //子集
Matrix = array[0..MaxSetSize, 0..MaxSetSize] of integer; //矩阵
var
N, K : integer;{k-subsets of n-set}
BinCoef : Matrix;{binomial coefficients} //二项式系数
procedure RankSubset (A : Subset;
var Rnk : integer);
var
i : integer;
begin
Rnk := 0;
for i := 1 to K do
Rnk := Rnk + BinCoef[A[i] - 1, i];
end; {RankSubset}
procedure UnrankSubset (Rnk : integer;
var A : Subset);
var
p, m, i : integer;
begin
m := Rnk;
for i := K downto 1 do
begin
p := i - 1;
repeat{find largest binomial coefficient less than m}
p := p + 1
until (BinCoef[p, i] > m);
m := m - BinCoef[p - 1, i];{reduce rank by that binomial coefficient}
A[i] := p;{the parameters in the binomial coefficient give the set
value}
end; {for}
end; {UnrankSubset}
//获得第一个子集
procedure GetFirstSubset (var A : Subset;
var Done : boolean);
var
i : integer;
begin
for i := 1 to K do{first subset is 1 2 ...}
A[i] := i;
A[K + 1] := N + 1;
Done := false;
end; {GetFirstSubset}
//获得下一个子集
procedure GetNextSubset (var A : Subset;
var Done : boolean);
var
i, j : integer;
begin
if (A[1] < N - K + 1) then{when A[1] is too big, last set has been reached}
begin
Done := false;
j := 0;
repeat{find smallest element that can be advanced }
j := j + 1
until (A[j + 1] > A[j] + 1);
A[j] := A[j] + 1;{advance it}
for i := 1 to j - 1 do{reset all smaller elements}
A[i] := i;
end {if then}
else
Done := true;
end; {GetNextSubset}
//计算二项式系数
procedure Pascal;{computes binomial coefficients}
var
i, p, r : integer;
begin
for i := 1 to MaxSetSize do
begin
BinCoef[0, i] := 0;
BinCoef[i, 0] := 1;
end; {for}
BinCoef[0, 0] := 1;
for p := 1 to MaxSetSize do
for r := 1 to p do{Pascal recursion}
BinCoef[p, r] := BinCoef[p - 1, r] + BinCoef[p - 1, r - 1];
end; {Pascal}
由于我没有组合数学的基础,无法理解 RankSubset 函数, UnrankSubset 函数,GetFirstSubset 函数和GetNextSubset 函数,
二项式系数在这里的作用是什么?
麻烦熟悉的朋友 指点一下
[解决办法]
坐等答案！楼下的回答！
