[algorytmika] Permutacje

W porównaniu do poprzedniego ([algorytmika] Problem), kolejny problem wydaje się być dziecinną igraszką.

Permutacje:
Mamy skończony ciąg n-elementowy.
Rozwiązaniem jest wypisanie wszystkich możliwych, niepowtarzających się permutacji tego ciągu.

Czyli jeżeli mamy ciąg wejściowy 1,2 odpowiedzią jest:
1,2
2,1

A dla ciągu 1,2,3:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

Zachodzi ogólna zależność: dla ciągu n-elementowego istnieje n! niepowtarzających się permutacji, gdzie działanie n! oznacza "n silnia" i jest zdefiniowane rekurencyjnie:
0!=1
n!=n-1!*n
dla liczb naturalnych dodatnich (n>0).

Jak zwykle proszę nie o kod źródłowy, tylko o niezwiązany z konkretnym językiem programowania algorytm.

Pozdrawiam

Rekurencja:

Dla każdego elementu po kolei zaznacz go jako zajęty [potem zwolnij] i rób:

1. weź pierwszy wolny element [gdy brak, zakończ i wypisz \n]
2. zaznacz jako zajęty
3. wypisz
4. dla wszystkich elementów zrób rekurencyjnie 1
5. zwolij element [dodane później [wstyd]]

--
Vogel [Delphi 6 PE]

Life is just a dream, you know...
[Cowboy Bebop]

Vogel, z całym dużym szacunkiem jakim Ciebie darzę, nie mogę się zgodzić z zaproponowanym algorytmem. Oczywiście pomysł aby ująć algorytm rekurencyjnie ma znaczenie KAPITALNE, ale w całym algorytmie zabrakło precyzji.

Aby nie było aż tak abstrakcyjnie, powiedzmy że nasz ciąg ma postać:
{a1,a2,a3....an}

na pewno ten algorytm jest bardzo blisko, ale w moim odczuciu to jeszcze nie jest rozwiązanie.

Pozdrawiam

To zapiszę w pseudokodzie (nigdy nie byłem dobry w pisaniu algorytmów punkt-po-punkcie).

dane[] zajęte[] ilość_danych;
zajęte = [b]false[/b];
[b]for[/b] j = 1 -> ilość_danych {
zajęte[j] = [b]true[/b];
push(j);
go(1);
pop();
}

go (ile) {
[b]for[/b] j = 1 -> ilość_danych {
[b]if[/b] [b]not[/b] zajęte[j] {
[b]if[/b] ile = ilość_danych - 1 {
wypisz(zawartość_stosu);
wypisz(j, '\n');
} else {
push(j);
go(ile + 1);
pop();
}
}
}

To nie jest żaden specyficzny język programowania, więc proszę się nie kłócić :P

--
Vogel [Delphi 6 PE]

Life is just a dream, you know...
[Cowboy Bebop]

W porównaniu do poprzedniego ([algorytmika] Problem), kolejny problem wydaje się być dziecinną igraszką.

Permutacje:
Mamy skończony ciąg n-elementowy.
Rozwiązaniem jest wypisanie wszystkich możliwych, niepowtarzających się permutacji tego ciągu.

Jak zwykle proszę nie o kod źródłowy, tylko o niezwiązany z konkretnym językiem programowania algorytm.

Pytanie: potrzebujesz dowolnego kodu, czy najlepszego (czytaj najszybszy).

--
Jest jeszcze jeden błąd ... :)

Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.

O ile mnie pamięć nie myli to taki kod pod pascalem zajmuje max 8 linijek, ale niestety nie pamiętam już jak to zrobiłem.
Wiem że należało wywoływać rekurencyjnie funkcje aż dojdzie do dwóch elmentów następnie je przestawić.... tak się zaczynało ale jak kończyło to niewiem. Jak będe miał chwilkę to może coś napisze.

O ile mnie pamięć nie myli to taki kod pod pascalem zajmuje max 8 linijek, ale niestety nie pamiętam już jak to zrobiłem.
Wiem że należało wywoływać rekurencyjnie funkcje aż dojdzie do dwóch elmentów następnie je przestawić.... tak się zaczynało ale jak kończyło to niewiem. Jak będe miał chwilkę to może coś napisze.

U mnie zajęło trochę więcej:

procedure P(Poz: Word; Ciag: string);
var
j: Word;
C: string;
begin
if Poz > Length(Ciag) then
Memo1.Lines.Add(Ciag);
for j := Poz to Length(Ciag) do
begin
C := Ciag;
C[j] := Ciag[Poz];
C[Poz] := Ciag[j];
P(Poz+1, C);
end;
end;
var
Ciag: string;
begin
Ciag:='12345';
P(1, Ciag);
end;

Kapustka: wiem, że nie chodziło ci o kod, ale tak jest prościej.

--
Jest jeszcze jeden błąd ... :)

Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.