[es] - Jedno pitanje

reiser

Član broj: 7895
Poruke: 2314

+102 Profil

^{22.04.2005. u 09:37 - pre 231 meseci}

Recimo da imam jedan niz od n elemanata. Kako napraviti sve varijacije bez ponavljanja niza ? Recimo, imam niz [1, 2, 3]. Kako izvesti :
[1, 2, 3]; [1, 3, 2]; [2, 1, 3]; [2, 3, 1]; [3, 1, 2]; [3, 2, 1]
Treba mi sto brzi algoritam.

Odgovor na temu

Toyo

Član broj: 45193
Poruke: 227
*.kovnet.co.yu.

+1 Profil

Re: Jedno pitanje

^{22.04.2005. u 11:10 - pre 231 meseci}

U nizu a, u repeat petlji ti je svakm prolazom sledeca permutacija.

Code:

const
  N=10;
type
  niz=array[1..N] of integer;

function NextPermute(var x:niz): Boolean;
procedure swap(i:integer; j:integer);
var
   temp : byte;
begin
     temp := x[i];
     x[i] := x[j];
     x[j] := temp;
end;
var
   k,j,r,s : integer;
begin
     k := n-1;
     while (k>0) and (x[k] > x[k+1]) do
           k:=k-1;
     if k<1 then
        result:=false
     else
        begin
          j := n;
          while x[k] > x[j] do
                j:=j-1;
          swap(j,k);
          r:=n;
          s:=k+1;
          while r>s do
                begin
                     swap(r,s);
                     r:=r-1;
                     s:=s+1;
                end;
          result:=true;
        end;
end;

var
  i,br: integer;
  a: niz;
begin
   br:=0;
   for i := 1 to N do
    a[i]:=i;
   repeat
    inc(br);
   until not nextpermute(a);
   writeln('Ukupno ', br,' permutacija');
   readln;
end.

Odgovor na temu

bancika
Branislav Stojkovic

Član broj: 24844
Poruke: 631
213.244.208.*

Sajt: www.diy-fever.com

+1 Profil

Re: Jedno pitanje

^{22.04.2005. u 15:57 - pre 231 meseci}

nema brze od O(n!) jer toliko permutacija ima od n elemenata.
jedino je razlika da li hoces rekurzivno ili ne...

Ride the rainbow, crack the sky

DIY gitare, pojacala i efekti www.diy-fever.com

Odgovor na temu