好难排列算法问题 ( 积分: 100 )

  • 主题发起人 主题发起人 mawp
  • 开始时间 开始时间
M

mawp

Unregistered / Unconfirmed
GUEST, unregistred user!
下列两表中的“人”和“队列”的个数都不确定,用什么样的算法可以将“人”和“队列”的各种组合输出出来呢?
人 队列
1 A
2
3
结果:在A一个队列的组合有6种,分别为:123、132、213、231、312、321
人 队列
1 A
2 B
3
结果:在A、B两个队列的组合有24种,分别为:
(A:无,B:123)、(A:无,B:132)
(A:无,B:213)、(A:无,B:231)
(A:无,B:312)、(A:无,B:321)
(A:1,B:23)、(A:1,B:32)
(A:2,B:13)、(A:2,B:31)
(A:3,B:12)、(A:3,B:21)
(A:12,B:3)、(A:21,B:3)
(A:13,B:2)、(A:31,B:2)
(A:23,B:1)、(A:32,B:1)
(A:123,B:无)、(A:132,B:无)
(A:213,B:无)、(A:231,B:无)
(A:312,B:无)、(A:321,B:无)
 
下列两表中的“人”和“队列”的个数都不确定,用什么样的算法可以将“人”和“队列”的各种组合输出出来呢?
人 队列
1 A
2
3
结果:在A一个队列的组合有6种,分别为:123、132、213、231、312、321
人 队列
1 A
2 B
3
结果:在A、B两个队列的组合有24种,分别为:
(A:无,B:123)、(A:无,B:132)
(A:无,B:213)、(A:无,B:231)
(A:无,B:312)、(A:无,B:321)
(A:1,B:23)、(A:1,B:32)
(A:2,B:13)、(A:2,B:31)
(A:3,B:12)、(A:3,B:21)
(A:12,B:3)、(A:21,B:3)
(A:13,B:2)、(A:31,B:2)
(A:23,B:1)、(A:32,B:1)
(A:123,B:无)、(A:132,B:无)
(A:213,B:无)、(A:231,B:无)
(A:312,B:无)、(A:321,B:无)
 
先排列 再归队
 
太烦了,思路是这样:
设人数HumanCount,队数TeamCount
1、先进行拆数字,把HumanCount拆成TeamCount个数的和,包括0。如9个人,3个队,则把9拆开,有0+0+9,1+0+8等等。
具体做可以用排列算法解决,即从10个数(包括0)中取3个数,得到各种排列方案(如012、013、123、124、125......),然后遍历这些排列,三个数和为9的方案留下。
2、对以上每一个人数分配方案进行人数分配
如对上面的排列:(2,2,5),对每一个队作排列
第一个队从9人中取2人
第二个队从剩下7人中取2人
...........

排列组合的程序:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TVarList =array of Variant;
Tform1 = class(TForm)
Button1: TButton;
procedure Button1Click(Sender: TObject);
public
{ Public declarations }
functiondo
PRocess(Order:boolean;Vars:TVarList;level:Integer;Parentvar:TVarList=nil):string;
//Vars:是要组合内容,可以是任何类型,Level:是组合个数,ParentVar是当前已在组合中的内容
function AddVar(Vars:TVarlist):string;//将排列内容添加到字符串数组中
function AddVar1(Vars:TVarlist):string;//将组合内容添加到字符串数组中
end;

var
form1: Tform1;
sList:TStringList;
implementation
uses StrUtils;
{$R *.dfm}
function Tform1.DOPRocess(Order:boolean;Vars: TVarList;
level: Integer;Parentvar:TVarList):string;
var
iCOunt:Integer;
begin
SetLength(Parentvar,Length(Parentvar) +1);
if Level >1 then
for iCount := Low(Vars) to High(Vars) -1do
begin
Parentvar[High(ParentVar)] := Vars[iCount];
do
PRocess(Order,Copy(Vars,iCount+1,High(vars)),Level-1,Parentvar);
end
else
for iCOunt := Low(Vars) to High(Vars)do
begin
Parentvar[High(ParentVar)] := Vars[iCount];
if Order then
sList.Add(Addvar(parentvar))
else
sList.add(Addvar1(parentvar));
end;
Result:=sList.Text;
if Level=0 then
Result:='';
end;

function Tform1.AddVar(Vars: TVarlist):string;
var
i,j :Integer;
strs:string;
sList:TStringList;
begin
sList:=TStringList.Create;
for i:= Low(Vars) to High(Vars)do
begin
strs:='';
for j:=i to i+High(Vars)do
begin
if j>High(Vars) then
strs:=strs+Vartostr(vars[j-High(Vars)-1])
else
strs:=strs+VartoStr(vars[j]);
end;
if sList.IndexOf(strs)=-1 then
sList.Add(strs);
end;
Result:=trim(sList.Text);
sList.Free;
end;

function Tform1.AddVar1(Vars: TVarlist):string;
var
i :Integer;
strs:string;
begin
for i:= Low(Vars) to High(Vars)do
strs:=strs+VartoStr(vars);
Result:=strs;
end;

procedure Tform1.Button1Click(Sender: TObject);
var
Humans:TVarList;
m,n:Integer;
begin
sList:=TStringList.Create;
m:=4;
n:=3;
SetLength(Humans,m);
Humans[0]:= 1;
Humans[1]:= 2;
Humans[2]:= 3;
Humans[3]:= 4;
showmessage(DOPRocess(true,Humans,n));//从m个中选n个,有顺序
showmessage(DOPRocess(false,Humans,n));//从m个中选n个,无顺序
sList.Free;
end;

end.
 
上面的搞些什么啊
function sq(s:array[1..n],i:integer);
var
j,k:integer;
begin
if i=n then
for j:=1 to ndo
write(s);
else
begin
sq(s,i+1);
for k:=i to ndo
begin
swap(s,s[k]);
sq(s,i+1);
swap(s,s[k]);
end;
end;
end;

看不懂就随便找一本组合数学的书看看蛮简单的
 
呵呵,楼上的帅哥,心浮气躁啊,校园高手吧
你没仔细看楼主的问题,楼主的问题其实主要不是排列算法,我写个排列算法是为方便楼主解决问题。
你这个函数是否想实现邻位互换算法?里面有多少错误,你自己编译一下数数看,我看不懂。
如果你不懂我在干什么,就把我的代码编译一下看看我到底搞些什么?很简单的不用看代码,粘贴下来编译就行,delphi会用吧。
 
多谢,你的思路和代码我仔细看了,可以实现,多加些代码就好了。以后还要向你多多请教。
 
后退
顶部