permutacja w C++

[Pniaq]

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

[Tomasz Rużycki]

... php/c5123/

[Pniaq]

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

[Tomasz Rużycki]

Nie wiem.

[Undre]

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 ?

[John Nash]

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]

Rekurencja o ile mi wiadomo obciąża mocno pamięć i w przypadku dużego zbioru byłby chyba problem na tym gruncie czyż nie ?

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.

[kadiii]

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

[Mbach]

to teraz skoro już macie permutacje, to naiszcie mi program który liczy wartość wyznacznika z Laplace`a potrzebne mi to

[Pniaq]

John Nash,
Wiec moze opiszesz mi to kawalek po kawalku bo ja dopiero zaczynam .
Bylbym wdzieczny

[John Nash]

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.

[Fibik]

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.

[arigo]

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'); 
}

[sardynki]

a teraz jak napisac program rozwiazujacy sudoku