Kombinatorické algoritmy

Následující algoritmy jsme si popisovali na cvičeních koncem listopadu s Jakubem Bystroněm. Generují permutace, kombinace, variace.

Deprecated: Assigning the return value of new by reference is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/highlight/pascal.php on line 5

program KombinaceASpol(input, output);

{
 Chybel jsem na permutace, ale jinak je to vice mene podle toho, co jsme s Jakubem
 Bystronem delali na cvicenich koncem listopadu. I ty permutace nejspis. -- Adam Nohejl
}
 

const
    maxn = 100;

var
    { parametry variace/kombinace/...: }
    n:          integer;
    k:          integer;
    
    pouzito:    array[1..maxn] of boolean; { byla dana cislice pouzita? }
    c:          array[0..maxn] of integer; { sem se ukladaji vysledky, 0 je pomocna pro kombinace }

{ Vypis globalni promenne c, viz vyse: }
procedure vypis;
var i : integer;
begin
    for i := 1 to k do
        write(' ', c[i]);
    writeln;
end;

{ Algoritmus: permutace(k) }
procedure permutace(i: integer);
var
    j   : integer;
begin
    if i>k then
        vypis
    else
        for j := 1 to k do
            if not pouzito[j] then
            begin
                c[i]            := j;
                pouzito[j]      := TRUE;
                permutace(i+1);
                pouzito[j]      := FALSE;
            end;
end;



{ Algoritmus: variace(n,k) - aneb permutace v blede modrem }
procedure variace(i: integer);
var
    j   : integer;
begin
    if i>k then
        vypis
    else
        for j:=1 to n do                    { Tim se lisi od permutaci. }
            if not pouzito[j] then begin
                c[i]        := j;
                pouzito[j]  := TRUE;
                variace(i+1);
                pouzito[j]  := FALSE;
            end;
end;

procedure kombinace(i: integer);
var
    j   : integer;
begin
    if i>k then
        vypis
    else
        for j:=c[i-1]+1 to n do             { Tim se lisi od variaci. }
            if not pouzito[j] then begin
                c[i]        := j;
                pouzito[j]  := TRUE;
                kombinace(i+1);
                pouzito[j]  := FALSE;
            end;
end;



var
    i   : integer;
begin   
    write('n: ');
    read(n);
    write('k: ');
    read(k);
    writeln;
    
    writeln('permutace(k):');
    for i:= 1 to maxn do
        pouzito[i]  := FALSE;
    permutace(1);
    writeln;
    
    writeln('variace(n,k):');
    for i:= 1 to maxn do
        pouzito[i]  := FALSE;
    variace(1);
    writeln;
    
    writeln('kombinace(n,k):');
    c[0] := 0;                      { Tohle nam pomuze pri "for j:=c[i-1]+1 to n do" }
    for i:= 1 to maxn do
        pouzito[i]  := FALSE;
    kombinace(1);
  
end.

Matfiz : KombinatorickéAlgoritmy

Kombinatorické algoritmy