INFOMAN брой 5
{
РЕШЕНИЕ НА ЗАДАЧА 2 ЗА 1998 ГОДИНА ОТ КОНКУРСА ПО ПРОГРАМИРАНЕ
НА СПИСАНИЕ PC MAGAZINE/BULGARIA
Дадени са N букви (сред които може и да има еднакви), представени със
символ от латинската азбука.Ако думи наричаме произволни последователнос-
ти от поне 1 буква, а изречения наричаме произволни последователности от
думи (поне 1 дума), разделени с интервали, да се напише програма, която
генерира всички различни изречения, в които всяка една буква от дадените
се среща точно по веднъж. Входът се задава като символен низ. Изходът са
всички възможни различни изречения, всяко на отделен ред.
РЕШЕНИЕ:
Задачата най-общо можем да разделим на 2 части:
1. Генериране на всички пермутации на дадените N букви
2. Намиране на всички разпадания на низа, получен от всяка генерирана
пермутация на последователност от няколко други низа.
Нека дадените букви са низа S и са N на брой. Генерирането на всички пер-
мутации на N елемента можем да направим по стандартния алгоритъм с пряка
размяна, който е един от най-ефективните известни. Алгоритъмът е рекурси-
вен. Той се вика първончално за обработка на N-те елемента на пермутация-
та. На всяка стъпка се извиква рекурсивна обработка на първите N-1 еле-
мента на пермутацията. След това се разменя последната цифра на текущата
пермутация с всеки от предходните елементи и се вика отново рекурсия за
предходните N-1 елемента. Когато N = 1, е намерена поредната пермутация.
Намирането на всички разпадания на един N-буквен низ на негови последова-
телности от поднизове е всъщност задачата за намиране на всички предста-
вяния на едно число като сума от положителни числа,като тяхната подредба
е от значение. Известно е,че броят разпадания на едно число N като подре-
дена сума от елементи е 2^(N-1).Можем да генерираме тези разпадания с ре-
курсивна процедура, която върти вложени цикли и внимава сумата от стойно-
стите на броячите на всеки от тях да не превишава N. Ако тази сума е N,
е намерено поредното разпадане.
За да постигнем по-голяма ефективност на алгоритъма не е нужно всеки път
да намираме всички разпадания на един низ на последователност поднизове.
Достатъчно е да намерим това веднъж и да си направим един списък от всич-
ки разпадания на N-буквен низ. Това правим в удобен за използване вид по
следния начин. За всяко разпадане пази по един N-елементов масив D[1..N],
в който отбелязваме в D[I] дали след I-тия елемент започва нова дума,т.е.
дали след него трябва да има интервал.Този масив D се получава много лес-
но. Нека например имаме разпадането на 7-буквен низ на низове с дължини
съответно 2, 1, 3 и 1. Тогава интервал трябва да има след буквите с номе-
ра 2, 3=2+1 и 6=2+1+3. След 7-мата буква няма нужда от интервал.Аналогич-
но на дадения пример и с помощтта на обяснения алгоритъм за намиране на
всички разпадания на низ на последователност от поднизове формираме един
списък от разпадания в посочения вид само веднъж - в началото на програ-
мата, когато е известна стойността на N. При намиране на поредната перму-
тация на дадения първоначално N-буквен низ, отпечатваме всичките разпада-
ния на тази пермутация. Алгоритъмът има времева сложност O(N!*2^N).
Входът и изходът на програмата са съответно от клавиатурата и на екрана,
но лесно могат да се пренасочат чрез символите "<", ">" от командния ред
на DOS.
Понеже сред дадените първоначално N букви може да има повтарящи се, тряб-
ва да игнорираме еднаквите пермутации на тези N букви, защото те ще дове-
Разликата в нея е,че тя генерира всички. Използва се същия алгоритъм за
генериране на пермутации, но се внимава да не се прави размяна на елемен-
ти, при която един елемент прескача или се разменя с еднакъв на него еле-
мент. Това гарантира, че в крайна сметка няма да се получат еднакви пер-
мутации. Програмата работи правилно до 10 буквени низове, но при желание
може да се компилира и за по-дълги низове (стига да имаме достатъно бърз
компютър и много място на твърдия диск).
Задачата може да се реши и с изцяло друг алгоритъм. Идеята е да направим
една рекурсивна процедура, която генерира всички изречения по следния на-
чин: За първа буква поставя всяка една от дадените букви.За следваща бук-
ва поставя всяка от останалите букви, както и символа интервал.За следва-
ща буква отново поставя всяка от останалите букви и интервал, ако генери-
раният на предната стъпка символ не е интервал и т.н. Когато се поставят
точно N символа, е генерирано изречение. След като вече няма продължение
(няма повече неизползвани букви на дадената стъпка), алгоритъма се връща
една стъпка назад. Този алгоритъм не е използван, защото има сложност от
порядъка на (N+1)^N, т.е. той е много по-неефективен от предходния.
}
{$R-} {$Q-} {$S-}
CONST MaxN = 10;
MaxDecomps = 512; {2^(MaxN-1)}
VAR S: string;
N,BrDecs: integer;
Decs: array[1..MaxDecomps,1..MaxN] of boolean;
Procedure Print; {Print all decompositions to N parts of permutation S}
Var Izr,I: integer;
Begin
for Izr:= 1 to BrDecs do
begin
for I:= 1 to N do
begin
Write(S[I]);
if Decs[Izr,I] then Write(' ');
end;
WriteLn;
end;
End;
Procedure GeneratePerm(K:byte); {Genarate all perms of first K chars of S}
Function CanExchange(I,K:byte): boolean;
Begin
for K:= I+1 to K do
if S[I] = S[K] then
begin CanExchange:=false; Exit; end;
CanExchange:=true;
End;
Var I: byte;
Swp: char;
Begin
if K = 1 then Print
else
begin
GeneratePerm(K-1);
for I:= 1 to K-1 do
if CanExchange(I,K) then
begin
Swp:=S[I]; S[I]:=S[K]; S[K]:=Swp;
GeneratePerm(K-1);
Swp:=S[I]; S[I]:=S[K]; S[K]:=Swp;
end;
end;
End;
Procedure ReadData;
Var Sum: byte;
D,DD: array[1..MaxN] of byte;
Procedure FindAllDecompositions(Poz:byte);
{Find all decompositions of S as ordered sum of positive numbers}
Procedure AddDecomposition;
Var i: byte;
Begin
Inc(BrDecs); FillChar(Decs[BrDecs],SizeOf(Decs[BrDecs]),false);
DD:=D;
for i:= 1 to Poz-1 do
begin
Decs[BrDecs][DD[i]]:=true;
DD[i+1]:=DD[i+1]+DD[i];
end;
End;
Var c: byte;
Begin
for c := N downto 1 do
begin
D[Poz]:=c;
Inc(Sum,c);
if Sum = N then
AddDecomposition
else if Sum < N then FindAllDecompositions(Poz+1);
Dec(Sum,c);
end;
End;
Begin
Write('Enter a sequence of several letters: ');
ReadLn(S); N:=length(S);
BrDecs:=0; Sum:=0;
FindAllDecompositions(1);
End;
BEGIN
ReadData;
GeneratePerm(N);
END.