求生成一组数的组合（加上200分） (200分)

B

baidh

Unregistered / Unconfirmed
GUEST, unregistred user!
请问如何生成下面的排列：
有一组数组 (a1,a2...an),(b1,b2...bm),...(z1,z2...zn),其中，
数组数不确定，每一数组中数的个数也不确定，
求：从以上数组中任选7个数字的组合：
条件：每一组数中最多包含7个数中的3个
(即：这7个数生成的数组与原始数组的交集数<=3个数)。
 
回去试试！
 
关注！
 
天！又是排列组合的问题... 我都做烦了
一个小建议：............................把这个问题放到“数据结构”分类中去如何？
 
复习一下数据结构[:D]
 
想.........
 
Done!
//仅考虑了结果的组合，而不是排列
//注：TBuffer类的代码请看 http://www.delphibbs.com/delphibbs/dispq.asp?lid=968511
function GetArrayBalls(A:array of Integer;
ArrayLen, MaxNumPerGrp, TotalNum:Integer):Integer;
var
Used:array of array of Boolean;
UsedNum:array of Integer;
Buffer:TBuffer;
proceduredo
Level(Level,StartLevel,StartPos:Integer);
var
i,j,s:Integer;
mstr:String;
begin
if Level=TotalNum then
begin
Inc(Result);
mstr:='';
for i:=0 to ArrayLen-1do
for j:=0 to A-1do
if Used[j] then
mstr:=mstr+Char(Byte('a')+i)+IntToStr(j)+' ';
mstr:=mstr+#13#10;
Buffer.WriteBuf(@mstr[1],Length(mstr));
exit;
end;
for i:=StartLevel to ArrayLen-1do
begin
if i=StartLevel then
s:=StartPos
else
s:=0;
for j:=s to A-1do
if (UsedNum<MaxNumPerGrp) and (UsedNum<A) then
begin
Inc(UsedNum);
Used[j]:=true;
do
Level(Level+1,i,j+1);
Used[j]:=false;
Dec(UsedNum);
end;
end;
end;
var
i:Integer;
begin
Result:=0;
SetLength(Used,ArrayLen);
for i:=0 to ArrayLen-1do
begin
SetLength(Used,A);
FillChar(Used[0],A*SizeOf(Boolean),0);
end;
SetLength(UsedNum,ArrayLen);
FillChar(UsedNum[0],ArrayLen*SizeOf(Integer),0);
Buffer:=TBuffer.Create;
do
Level(0,0,0);
Form1.Memo1.Text:=Buffer.AsString;
Buffer.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
A:array of Integer;
i:Integer;
begin
SetLength(A,SpinEdit3.Value);
//SpinEdit3.Value=4 分组个数
for i:=0 to SpinEdit3.Value-1do
A:=StrToInt(StringGrid1.Cells[0,i+1]);
//eg: A=(5,4,2,4)
Caption:=IntToStr(GetArrayBalls(A,SpinEdit3.Value,SpinEdit1.Value,SpinEdit2.Value));
//eg: GetArrayBalls(A,4,3,7);
4:分组个数 3:每组中最多可以被选取的球数 7:要取的总球数
end;

实验结果： 5460个解
a0 a1 a2 b0 b1 b2 c0
a0 a1 a2 b0 b1 b2 c1
a0 a1 a2 b0 b1 b2 d0
...
...
b2 b3 c0 c1 d0 d1 d2
b2 b3 c0 c1 d0 d1 d3
b2 b3 c0 c1 d0 d2 d3
b2 b3 c0 c1 d1 d2 d3

由于这个问题属于排列组合问题，解的个数会随着ArrayLen, MaxNumPerGrp, TotalNum的增长而
急剧上升。一般说来，当ArrayLen>10的时候，就已经不可计算了。
满意否？
 
你的分出的真冤枉，怎么样，多给点儿。
 
优化后的核心算法：
proceduredo
Level(Level,StartLevel,StartPos:Integer);
var
i,j,s:Integer;
mstr:String;
begin
if Level=TotalNum then
begin
Inc(Result);
mstr:='';
for i:=0 to ArrayLen-1do
for j:=0 to A-1do
if Used[j] then
mstr:=mstr+Char(Byte('a')+i)+IntToStr(j)+' ';
mstr:=mstr+#13#10;
Buffer.WriteBuf(@mstr[1],Length(mstr));
exit;
end;
s:=StartPos;
//初始化起始位置，确保从前往后取球
for i:=StartLevel to ArrayLen-1do
begin
if (UsedNum<MaxNumPerGrp) and (UsedNum<A) then
for j:=s to A-1do
begin
Inc(UsedNum);
Used[j]:=true;
do
Level(Level+1,i,j+1);
Used[j]:=false;
Dec(UsedNum);
end;
s:=0;
//起始位置复零
end;
end;

另：
你的另外两个帖子现在还没有人回答，你可以选择删除它们或者请求版主把分数回给你自己。
 
请问creation-zy：
你写的程序中的“SpinEdit”指的是什么控件？
能不能把你的EMAIL留下？
谢谢。
 
在Samples面板里面，只能输入整数，还可以通过鼠标点击上下按钮改变数值的大小。
Mail见： http://www.delphibbs.com/delphibbs/dispq.asp?lid=985431
再次建议将此问题转移到“基础篇-数据结构”分类（点击一下“编辑”按钮）。
 
咳,我不会做.
 
creation-zy：
你写的代码我试了一下，感觉它是在理想状况下运行，我举一个例了，请试一下：
数组为：（3，13），（02，12，18，33），（10，21），（09 26），（08，15，17，31），
（7，14，23），（空），（1，6，20），（19，22，25，30），（16），（04，27），（24），（28），
（5，11，29，32）共14个数组，每组里取不超过3个数，生在的组合为7个数。套用小球的说法：
X种不同颜色的小球，不同种类小球个数不一样，要放在一个盒子里，每次放7个，每种颜色的球每次最多不超过3个，
有多少种放法，是什么？
 
结果太多了！我仅计算前面10组就用了43秒——476710种组合。
我修改了源代码，让它仅计算结果数，并不显示结果：
if Level=TotalNum then
begin
Inc(Result);
{mstr:='';
//注释掉 ***********
for i:=0 to ArrayLen-1do
for j:=0 to A-1do
if Used[j] then
mstr:=mstr+Char(Byte('a')+i)+IntToStr(j)+' ';
mstr:=mstr+#13#10;
Buffer.WriteBuf(@mstr[1],Length(mstr));} //************
exit;
end;

用了711毫秒算出有4257432种组合。
还有，我的结果是按照颜色分类的，要得到你给每个球定的标号，应该进行映射：
eg:
b2 b3 d1 e3 f0 h1 h2 -> 18 33 26 31 7 6 20
 
接受答案了.
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
Y
如何从任意个数中抽取出任意个数的全部组合。(200分)
回复
7
查看
387
yuleibo
Y
D
排列组合的问题(200分)
回复
19
查看
150
dxpjj
D
G
从任意M个数中选出N个数的所有组合数(100分)
回复
15
查看
477
张剑波
张
P
有关数据类型转换的问题,大家帮一把.(200分)
回复
3
查看
257
P_O
P
顶部