permutacja w C++
- Pniaq
- Użytkownik
- Posty: 39
- Rejestracja: 5 kwie 2006, o 18:01
- Płeć: Mężczyzna
- Lokalizacja: Dąbrowa Górnicza
- Podziękował: 3 razy
- Pomógł: 2 razy
permutacja w C++
Ma ktos pojecie jak napisac program ktory bedzie mi wypisywal wszystkie permutacje danego zbioru np.
Podaje mu elementy a,b,c
No to robi
a,b,c
a,c,b
b,a,c
b,c,a
c,b,a
c,a,b
Babka nam mowila ze trzeba to jakos rekurencja ruszyc . . .
Dzieks z gory
Podaje mu elementy a,b,c
No to robi
a,b,c
a,c,b
b,a,c
b,c,a
c,b,a
c,a,b
Babka nam mowila ze trzeba to jakos rekurencja ruszyc . . .
Dzieks z gory
- Tomasz Rużycki
- Użytkownik
- Posty: 2970
- Rejestracja: 8 paź 2004, o 17:16
- Płeć: Mężczyzna
- Lokalizacja: Suchedniów/Kraków
- Podziękował: 4 razy
- Pomógł: 293 razy
- Pniaq
- Użytkownik
- Posty: 39
- Rejestracja: 5 kwie 2006, o 18:01
- Płeć: Mężczyzna
- Lokalizacja: Dąbrowa Górnicza
- Podziękował: 3 razy
- Pomógł: 2 razy
permutacja w C++
Dzieks
A czy wiesz moze o co tu chodzi
#include
#include
using namespace std;
void char_permutation(char str[],char append[])
{
int length=strlen(str);
if(length)
{
for(int i=0;i<length;++i)
{
char* str1=new char[length+1];
int cnt;
int cnt2;
for(cnt=0,cnt2=0;cnt<length;++cnt,++cnt2)
{
if(cnt==i)
{
str1[cnt]=str[++cnt2];
continue;
}
else
str1[cnt]=str[cnt2];
}
str1[cnt]='\0';
int alength=strlen(append);
char* append1=new char [alength+2];
strncpy(append1,append,alength);
append1[alength]=str;
append1[alength+1]='\0';
char_permutation(str1,append1);
delete [] str1;
delete [] append1;
}
}
else
{
cout<<append<<endl;
}
}
int main()
{
char str[]="ABC";
char append[]="\0";
char_permutation(str,append);
cout<<"Complete!"<<endl;
return 0;
}
tak krok po kroku
A czy wiesz moze o co tu chodzi
#include
#include
using namespace std;
void char_permutation(char str[],char append[])
{
int length=strlen(str);
if(length)
{
for(int i=0;i<length;++i)
{
char* str1=new char[length+1];
int cnt;
int cnt2;
for(cnt=0,cnt2=0;cnt<length;++cnt,++cnt2)
{
if(cnt==i)
{
str1[cnt]=str[++cnt2];
continue;
}
else
str1[cnt]=str[cnt2];
}
str1[cnt]='\0';
int alength=strlen(append);
char* append1=new char [alength+2];
strncpy(append1,append,alength);
append1[alength]=str;
append1[alength+1]='\0';
char_permutation(str1,append1);
delete [] str1;
delete [] append1;
}
}
else
{
cout<<append<<endl;
}
}
int main()
{
char str[]="ABC";
char append[]="\0";
char_permutation(str,append);
cout<<"Complete!"<<endl;
return 0;
}
tak krok po kroku
- Tomasz Rużycki
- Użytkownik
- Posty: 2970
- Rejestracja: 8 paź 2004, o 17:16
- Płeć: Mężczyzna
- Lokalizacja: Suchedniów/Kraków
- Podziękował: 4 razy
- Pomógł: 293 razy
- Undre
- Użytkownik
- Posty: 1430
- Rejestracja: 15 lis 2004, o 02:05
- Płeć: Mężczyzna
- Lokalizacja: UĆ
- Podziękował: 3 razy
- Pomógł: 92 razy
permutacja w C++
Ciekawy programik, pewnie dłuuuuugo bym sam produkował taką koncepcję, pytanie jednak co ze zbiorami wieloelementowymi ? Rekurencja o ile mi wiadomo obciąża mocno pamięć i w przypadku dużego zbioru byłby chyba problem na tym gruncie czyż nie ?
-
- Użytkownik
- Posty: 15
- Rejestracja: 25 kwie 2006, o 14:49
- Płeć: Mężczyzna
- Lokalizacja: Princeton
- Podziękował: 3 razy
- Pomógł: 1 raz
permutacja w C++
Ale sama analiza trudna wcale nie jest. Banalna wrecz - wystarczy znajomosc paru podstawowych komend, zastosowanie funkcji bibliotecznych iostream i string, ktore kazdy, kto mial stycznosc z tym jezykiem zna (a jak nie, to mozna doczytac w manualu). Najprosciej by bylo wytlumaczyc wykonujac przykladowy program (czyli dokladnie w takiej formie, w jakiej jest) i wskazac co w danej chwili sie dzieje. Tylko to by duzo zajelo, bo w funkcji jest petla, w ktorej z kolei jest jeszcze jedna petla, a do tego rekurencja (w petli zreszta)... Jakby byly jakies pytania - sluze pomoca.
- juzef
- Użytkownik
- Posty: 890
- Rejestracja: 29 cze 2005, o 22:42
- Płeć: Mężczyzna
- Lokalizacja: Koszalin
- Pomógł: 66 razy
permutacja w C++
Jeśli dobrze rozumiem działanie tego algorytmu, to złożoność pamięciowa jest liniowa. Biorąc pod uwagę, że obliczeniowo nie da się zejść poniżej n!, zużycie pamięci jest pomijalne.Undre pisze:Rekurencja o ile mi wiadomo obciąża mocno pamięć i w przypadku dużego zbioru byłby chyba problem na tym gruncie czyż nie ?
- kadiii
- Użytkownik
- Posty: 642
- Rejestracja: 20 gru 2005, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 130 razy
permutacja w C++
Tak sobie myślę, że algorytm można, dla większej przejrzystości, oprzeć na systemach liczbowych. Trzeba by poprostu wypisać wszystkie liczby od ( n do n-1-tej ) +1 do n do n dla n-elementowej permutacji w systemie n-tym. Każdy jeden element byłby określony przez jedną liczbę. Taka moja idea, myślę, że raczej dobra a dużo prostsza do zrozumienia. ( jakby był jakiś błąd to walcie śmiało, nie myślałem nad tym długo). Pozdrowienia dla myślących
-
- Użytkownik
- Posty: 15
- Rejestracja: 25 kwie 2006, o 14:49
- Płeć: Mężczyzna
- Lokalizacja: Princeton
- Podziękował: 3 razy
- Pomógł: 1 raz
permutacja w C++
Calego za Ciebie nie przeanalizuje. Podstawowa wiedza z C++ by sie przydala. Poczytaj troche (naprawde nie ma tego duzo, znajdz jakis kurs albo cos), a gdyby byly jakies watpliwosci - pisz. Opisywanie kawalek po kawalku byloby zbyt zmudne.
-
- 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
permutacja w C++
Szkoda czasu na analizę tak marnego algorytmu.
To alokowanie jest jedynie stratą czasu (pamięci też, ale niewiele...).
Wszystko można, i należy robić 'w miejscu' (zwykła zamiana pary znaków),
Parametr 'append' jest zbędny - wystarczy jawnie podać liczbę znaków tego str,
która podlega permutacji... przy okazji nie będzie potrzeby obliczania długości - n! razy.
Permutację ciągu o długości N rozkładamy na N-1 permutacji ciągów o dł. N-1,
które tworzymy przez zamianę znaków: str :=: str[N], i = 1..N-1
Mamy prostą rekurencję, bez tych wszystkich zbędnych udziwnień - przekopiowywanie, alokowanie, appendy, itp.
To alokowanie jest jedynie stratą czasu (pamięci też, ale niewiele...).
Wszystko można, i należy robić 'w miejscu' (zwykła zamiana pary znaków),
Parametr 'append' jest zbędny - wystarczy jawnie podać liczbę znaków tego str,
która podlega permutacji... przy okazji nie będzie potrzeby obliczania długości - n! razy.
Permutację ciągu o długości N rozkładamy na N-1 permutacji ciągów o dł. N-1,
które tworzymy przez zamianę znaków: str :=: str[N], i = 1..N-1
Mamy prostą rekurencję, bez tych wszystkich zbędnych udziwnień - przekopiowywanie, alokowanie, appendy, itp.
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
permutacja w C++
ja bym z kolei proponowal cos prostego -zrodla w C dla malej liczby elementow sprawdza sie bardzo dobrze natomiast dla wiekszych trzeba wprowadzic pewne poprawki.
Kod: Zaznacz cały
#include <stdio.h>
void permutacja(int t[], int max);
void wypisz(int t[], int max);
long silnia(int n) {
int i;
long tmp=1;
for(i=2;i<=n;i++)
tmp*=i;
return tmp;
}
int main(void)
{
int t[] = { 1, 2, 3};
int MAX=sizeof(t)/sizeof(t[0]);
int i, j;
wypisz(t, MAX);
for (i = 0; i < silnia(MAX) -1 ; i++) {
permutacja(t, MAX);
wypisz(t, MAX);
}
return 0;
}
/* permutacja: generuje nastepnik permutacyjny dla zadanego szeregu
liczb
*/
void permutacja(int t[], int max)
{
int i, j, k;
if (max < 2)
return;
/* wyznaczanie pierwszego od prawej elementu
* mniejszego niz jego sasiad z prawej strony
*/
i = max - 1;
while ((i > 0) && (t[i - 1] >= t[i]))
i--;
/* wyznaczanie elementu wiekszego od znalezionego */
if (i > 0) {
j = max;
while ((j > 0) &&(t[j - 1] <= t[i - 1]))
j--;
}
/* zamiana miejscami dwoch znalezionych wyzej elementow */
if ((i > 0) && (j > 0)) {
k = t[i - 1];
t[i - 1] = t[j - 1];
t[j - 1] = k;
}
/* odbicie lustrzane szeregu elementow od indeksu i+1 do konca
tablicy
*/
for (i++, j = max; i < j; i++, j--) {
k = t[i - 1];
t[i - 1] = t[j - 1];
t[j - 1] = k;
}
}
/* wypisz: wypisuje zawartosc tablicy
*/
void wypisz(int t[], int max)
{
int i;
for (i = 0; i < max; i++)
printf("%d%c", t[i], (i < max - 1) ? ' ' : '\n');
}