Order is an important concept in mathematics and in computer science. For example, Zorn's Lemma states: ``a partially ordered set in which every chain has an upper bound contains a maximal element.'' Order is also important in reasoning about the fix-point semantics of programs.
This problem involves neither Zorn's Lemma nor fix-point semantics, but does involve order.
Given a list of variable constraints of the form x < y, you are to write a program that prints all orderings of the variables that are consistent with the constraints.
For example, given the constraints x < y and x < z there are two orderings of the variables x, y, and z that are consistent with these constraints: x y z and x z y.
The input consists of a sequence of constraint specifications. A specification consists of two lines: a list of variables on one line followed by a list of contraints on the next line. A constraint is given by a pair of variables, where x y indicates that x < y.
All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the contraints in a specification.
Input is terminated by end-of-file.
For each constraint specification, all orderings consistent with the constraints should be printed. Orderings are printed in lexicographical (alphabetical) order, one per line. Characters on a line are separated by whitespace.
Output for different constraint specifications is separated by a blank line.
a b f g a b b f v w x y z v y x v z v w v
abfg abgf agbf gabf wxzvy wzxvy xwzvy xzwvy zwxvy zxwvy
Při programování úlohy jsem použil v podstatě matici incidencí. Pro indexaci jsem použil rovnou názvy proměných a pravidlem je: Když TmpData['x','y']=True pak x < y. Toho pak využívám při kontrole správnosti vygenerované posloupnosti.
Úloha podle mého názoru představuje problém prohledávání do šířky (abecední seřazení). Pro řešení jsem se nakonec rozhodl pro generování všech možných cest a při každém kroku (přidání proměnné) kontroluji správnost posledního přidaného znaku (tedy zda není menší než již obsažené proměnné).
Nejspíše se tedy nejedná o žádný standardní algoritmus.
Časová složitost algoritmu se skládá ze dvou smyček: generovací a kontrolní. Protože generovací smyčka bude mít v nejhorším případě složitost N! (N je počet proměnných) a kontrolní smyčka prochází v každém kroku M-1 proměnných (M je počet proměnných v již vygenerované posloupnosti) bude celková asymptotická složitost:
N!(N-1)! tedy (N!)2Je možné, že existuje způsob, jak tuto časovou složitost snížit, bohužel mi ovšem tato metoda není známa.
První procedura kontroluje správnost syntaxe (počet řádků). Následně je začne načítat. Liché řádky jako definice abecedy (a zároveň délku výsledných posloupností). Sudé řádky jako definice pravidel.
Po načtení sudého řádku jím naplní matici TmpData a zavolá rekurzivní proceduru GenOrders.
procedure TForm1.BtnRunClick(Sender: TObject);
var NLine,i:Integer;
DefS,TmpS: String;
begin
if MemoIn.Lines.Count<2 then
begin MemoLog.Lines.Add('ERROR - Too few lines!'); Exit; end;
if (MemoIn.Lines.Count mod 2)<>0 then
begin MemoLog.Lines.Add('ERROR - Uneven count of lines!'); Exit; end;
for NLine:=0 to MemoIn.Lines.Count-1 do
if(NLine mod 2)=0 then begin
GenCount:=0; ConCount:=0;
DefS:=MemoIn.Lines[NLine];
while Pos(' ',DefS)>0 do Delete(DefS,Pos(' ',DefS),1);
MemoLog.Lines.Add('Starting new specification ['+DefS+'] with '+IntToStr(Length(DefS))+' variables.');
DefS:=';'+DefS;
for i:=0 to 26*26 do TmpData[Chr(Ord('a')+i div 26),Chr(Ord('a')+i mod 26)]:=False;
end else begin
TmpS:=Trim(MemoIn.Lines[NLine]);
while Pos(' ',TmpS)>0 do Delete(TmpS,Pos(' ',TmpS),1);
for i:=1 to Length(TmpS) do if Pos(TmpS[i],DefS)<1 then
begin MemoLog.Lines.Add('ERROR - '+IntToStr(i div 2+1)+'. char on '+IntToStr(NLine+1)+'. line is not in definition!'); Exit; end;
while Length(TmpS)>0 do begin
TmpData[TmpS[1],TmpS[2]]:=True;
Delete(TmpS,1,2);
end;
Delete(DefS,1,1);
GenOrders(DefS,'');
MemoLog.Lines.Add('Generating orderings finished. With steps: generator '+IntToStr(GenCount)+'; controler '+IntToStr(ConCount));
end;
MemoLog.Lines.Text:=copy(MemoLog.Lines.Text,1,Length(MemoLog.Lines.Text)-2);
end;
Druhá procedura generuje "všechny" posloupnosti. Jako paramtery dostává již vygenerovanou posloupnost a řetězec zatím nepoužitých proměných. Podmínkou pro generování posloupností v pořadí dle abecedy vyžaduje, aby byla abeceda definována dle abecedy! (Toto samozřejmě lze odstranit seřazením abecedy)
Pro optimalizaci jsem do generování zahrnul kontrolu správnosti přidávané proměnné (místo kontroly a hotové posloupnosti). Rekurze končí ve chvíli kdy posloupnost obsahuje všechny proměnné. (není co přidávat)
procedure GenOrders(SubDef,InputS:String);
var i:Integer; s:String;
begin
for i:=1 to Length(SubDef) do begin
Inc(GenCount);
s:=SubDef; Delete(s,i,1);
if AcceptOrder(InputS+SubDef[i]) then
GenOrders(s,InputS+SubDef[i]);
end;
if(Length(SubDef)=0)then Form1.MemoOut.Lines.Add(InputS);
end;
Třetí je funkce pro kontrolu posloupnosti, tedy pouze poslední proměnné posloupnosti. Původně jsem kontroloval celou posloupnost po jejím vygenerování, ale pro optimalizaci provádím kontrolu při každém přidání proměnné. Funkce vrací hodnotu True v případě, že poslední proměnná namá být menší než libovolná předchozí.
function AcceptOrder(InputS:String):Boolean; var i:Integer; begin for i:=1 to Length(InputS)-1 do begin Result:=not TmpData[InputS[Length(InputS)],InputS[i]]; if not Result then exit; Inc(ConCount); end; Result:=True; end;
Funkce obsahují také obsluhu prměnných "ConCount" a "GenCount", které jsou určeny pro načítání průchodů programových smyček.