[C++] Permutacje
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[C++] Permutacje
Witam!
Mam takie zadanie:
Napisz program, który dla zbioru n-elementowego podanego z zewnątrz wypisze wszystkie jego permutacje. Funkcji rekurencyjnej przekazujemy jako argumenty tablicę oraz indeks elementu, tak ma wyglądać prototyp funkcji:
void permutacje (int T[4], int index);
W odwołaniu rekurencyjnym funkcja wywołuje się z indeksem o 1 większym. To cała treść z podręcznika.
i właśnie z tym jest problem, bo znam algorytm iteracyjny na wypisywanie wszystkich permutacji zbioru (oczywiście w kolejności leksykograficznej), ale mam narzucony tutaj sposób w jaki to mam zrobić, a ja koniecznie chcę to tak zrobić. Mimo że zadanie nie obowiązywało mnie w szkole (jest w podręczniku ale nauczyciel pominął - są podejrzenia że dlatego że za trudne). Bardzo mi zależy na tym, aby lepiej pojąć rekurencję. Pomoże ktoś?
Mam takie zadanie:
Napisz program, który dla zbioru n-elementowego podanego z zewnątrz wypisze wszystkie jego permutacje. Funkcji rekurencyjnej przekazujemy jako argumenty tablicę oraz indeks elementu, tak ma wyglądać prototyp funkcji:
void permutacje (int T[4], int index);
W odwołaniu rekurencyjnym funkcja wywołuje się z indeksem o 1 większym. To cała treść z podręcznika.
i właśnie z tym jest problem, bo znam algorytm iteracyjny na wypisywanie wszystkich permutacji zbioru (oczywiście w kolejności leksykograficznej), ale mam narzucony tutaj sposób w jaki to mam zrobić, a ja koniecznie chcę to tak zrobić. Mimo że zadanie nie obowiązywało mnie w szkole (jest w podręczniku ale nauczyciel pominął - są podejrzenia że dlatego że za trudne). Bardzo mi zależy na tym, aby lepiej pojąć rekurencję. Pomoże ktoś?
-
- Użytkownik
- Posty: 971
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 75 razy
[C++] Permutacje
Tam ma być chyba nie 4, ale N - liczba elementów.
wypełniamy tablicę, np.: T = {1,2,3,4};
i ciach:
permutacje(T, 0);
Nie sprawdzałem czy to działa...
Kod: Zaznacz cały
#define N 4
inline void swap(int &a, int &b)
{ int c = a; a = b; b = c; }
void out(int T[])
{
for(int i = 0; i < N; i++) cout << T[i]; // 1234 bez rozdzielania...
cout < endl; // nowa linia;
}
void permutacje (int T[N], int ix) // ix = 0..N-1
{
if( ix < N-1 )
{
for(int i = ix; i < N; i++)
{
swap(T[ix], T[i]); // zamienia dwa elementy miejscami
permutacje(T, ix+1);
swap(T[ix], T[i]); // przywracamy
}
}
else out(T); // drukujemy wszystkie elementy
}
i ciach:
permutacje(T, 0);
Nie sprawdzałem czy to działa...
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[C++] Permutacje
Działa i to jak! Jest przepięknie, dokładnie o to mi chodziło Zabieram się za analizowanie. Bardzo, ale to bardzo dziękuję!-- 16 lut 2011, o 23:44 --Jednak jeszcze pomęczę... Koniec końców napisałem coś takiego:
jednak dla N=3 odpowiednio tworzy tablicę T={a,b,c}, ale wynikiem jest:
abc
acb
bac
bca
cba
cab
czyli końcówka (cba, cab) nie jest w kolejności leksykograficznej.. Jak to naprawić?
Kod: Zaznacz cały
#include <iostream>
using namespace std;
inline void swap(int &a, int &b)
{ int c = a; a = b; b = c; }
void out(char T[], int N)
{
for(int i = 0; i < N; i++) printf("%c", T[i]);
printf("
");
}
void permutacje (char T[], int ix, int N)
{
if( ix < N-1 )
{
for(int i = ix; i < N; i++)
{
swap(T[ix], T[i]);
permutacje(T, ix+1, N);
swap(T[ix], T[i]);
}
}
else out(T, N);
}
int main()
{
int N,t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &N);
char T[N];
//tworze tablice pierwszych N liczb alfabetu, to dla nich bede wypisywal permutacje
for(int i=0; i<N; i++)
{
T[i]=97+i;
}
permutacje(T, 0, N);
}
cout<<endl;
system("pause");
return 0;
}
abc
acb
bac
bca
cba
cab
czyli końcówka (cba, cab) nie jest w kolejności leksykograficznej.. Jak to naprawić?
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[C++] Permutacje
Z 4 było tak samo.. Wypisywał np 1432, 1423. Czyli czy to jest alfabet czy nie, efekt ten sam. Pozostanę już przy alfabecie (bo tak mam w specyfikacji zadanka). Widocznie drobny błąd jest gdzie indziej.
Zamieniłem:
na:
i teraz dla N=3 (tworzy tablicę T={a,b,c}) wypisuje:
cab
cba
bca
bac
acb
abc
czyli dokładnie to o co mi chodzi... tylko na odwrót Czyli teraz jakoś pokombinować aby on ten stos tworzył na odwrót? Tędy droga? Bo kolejność jest jaka być powinna, tylko od tyłu. Wystarczy zamienić kolejność i będzie leksykograficznie..
[EDIT]: co ja wygaduję, też jest źle..
Zamieniłem:
Kod: Zaznacz cały
void permutacje (char T[], int ix, int N)
{
if( ix < N-1 )
{
for(int i = ix; i < N; i++)
{
swap(T[ix], T[i]);
permutacje(T, ix+1, N);
swap(T[ix], T[i]);
}
}
else out(T, N);
}
na:
Kod: Zaznacz cały
void permutacje (char T[], int ix, int N)
{
if( ix < N-1 )
{
for(int i = N-1; i >= ix; i--)
{
swap(T[ix], T[i]);
permutacje(T, ix+1, N);
swap(T[ix], T[i]);
}
}
else
{
out(T, N);
}
}
cab
cba
bca
bac
acb
abc
czyli dokładnie to o co mi chodzi... tylko na odwrót Czyli teraz jakoś pokombinować aby on ten stos tworzył na odwrót? Tędy droga? Bo kolejność jest jaka być powinna, tylko od tyłu. Wystarczy zamienić kolejność i będzie leksykograficznie..
[EDIT]: co ja wygaduję, też jest źle..
Ostatnio zmieniony 17 lut 2011, o 21:16 przez adambak, łącznie zmieniany 1 raz.
[C++] Permutacje
sprawdzone
Kod: Zaznacz cały
void init(){ //by zacząć od pierwszej Value[i]<Value[i+1]
int i;
for(i=0; i<N; i++)
Value[i]=i;
}
void swap(int a, int b){
unsigned char t;
t=Value[a]; Value[a]=Value[b]; Value[b]=t;
}
void getNext() {
int i = N - 1;
while (Value[i-1] >= Value[i]) i = i-1;
int j = N;
while (Value[j-1] <= Value[i-1]) j = j-1;
swap(i-1, j-1);
i++; j = N;
while (i < j) {
swap(i-1, j-1);
i++;
j--;
}
}
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[C++] Permutacje
Tak, dziękuję, ale znam ten algorytm Moim problemem jest to że koniecznie chcę to zrobić rekurencyjnie(patrz początek tematu). W dodatku mam narzucony prototyp funkcji: void permutacje (int T[4], int index);
Może i jestem nudny i powinna mi wystarczyć iteracja, ale skoro takie zadanko znalazłem w podręczniku a mam wciąż problemy z rekurencją to chcę to zrobić rekurencyjnie dla przećwiczenia
Może i jestem nudny i powinna mi wystarczyć iteracja, ale skoro takie zadanko znalazłem w podręczniku a mam wciąż problemy z rekurencją to chcę to zrobić rekurencyjnie dla przećwiczenia
-
- Użytkownik
- Posty: 971
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 75 razy
[C++] Permutacje
Tam chodzi o to, że musimy przekazywać do permutacja() 'posortowane' od tego ix do końca.
ix = 0; potem wywołuje w tej pętli i = ix do N-1:
i = 0: a|bcd, dobrze, bo bcd jest posortowane;
i = 1: b|acd, tu też ok - acd jest w dobrej kolejności,
i = 2: c|bad, źle, powinno być c|abd
i = 3: d|bca - też źle...
dla i > 1 jest nieprawidłowa kolejność, bo ta jedynka ma być zawsze druga, a nie gdzieś dalej.
zatem trzeba zmienić fragment w pętli:
ten swap też chyba musisz poprawić - char nie int, bo używasz teraz tablicy char *T, czyli zwyczajny ciąg znaków, a nie liczby int.
ix = 0; potem wywołuje w tej pętli i = ix do N-1:
i = 0: a|bcd, dobrze, bo bcd jest posortowane;
i = 1: b|acd, tu też ok - acd jest w dobrej kolejności,
i = 2: c|bad, źle, powinno być c|abd
i = 3: d|bca - też źle...
dla i > 1 jest nieprawidłowa kolejność, bo ta jedynka ma być zawsze druga, a nie gdzieś dalej.
zatem trzeba zmienić fragment w pętli:
Kod: Zaznacz cały
void permutacje (char T[], int ix, int n)
{
if( ix < n-1 )
{
for(int i = ix; i < n; i++)
{
swap(T[ix], T[i]);
permutacje(T, ix+1, n);
}
// przywracamy porządek;sytuacja jest taka: n|123...n-1, a ma być 1234...n,
// czyli przesuwamy wszystko o 1 do przodu, a ten pierwszy na koniec
char c = T[ix];
for(int i = ix; i < n-1; i++) T[i] = T[i+1];
T[n-1] = c; // można to przerobić na funkcję, a tu tylko ciach: move(T, ix, n)
}
else out(T, N);
}