Funkcja permutacji

Odpowiedz Nowy wątek
2007-01-13 20:55

Rejestracja: 13 lat temu

Ostatnio: 1 godzina temu

0

Odrazu zaznaczam ze szukalem na forum i nie znalazlem tego co chzialem.
Oto funkcja z mojego programu ktora przeprowadza permutacje:

int permutacja(int m, int t[])
{
    int i, j, k;
    if (m < 2)
    return t[m];

// wyznaczanie pierwszego od prawej elementu mniejszego niz jego sasiad z prawej strony

    i = m - 1;
    while ((i > 0) && (t[i - 1] >= t[i]))
        i--;

// wyznaczanie elementu wiekszego od znalezionego 
if (i > 0) 
    {
        j = m;
        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 = m; i < j; i++, j--) 
    {
        k = t[i - 1];
        t[i - 1] = t[j - 1];
        t[j - 1] = k;
    }
 for(i=0;i<m;i++)                                        
        cout<<t[i]<<"->";
 cout<<t[0]<<endl;
 return t[m];
}

Niech m=5
A to moja tablica t[m]={1,2,3,4,5}
I tera z ta funkcja za kazdym wywolanie daje inna permutacje i o to mi chodzi

for (i=0;i<silnia(m)/m-1;i++)
    permutacja(m,t);
        droga = odleglosc(odl,m,t)

I ona ladnie wyswietla mi te mozliwosci wszystkie a dzieki for (i=0;i<silnia(m)/m-1;i++) temuwyswietla tytlko kombinacje wszystkich mozliwosci bez zmieniania pierwszego miejsca

Ale jesli na pierwszym miejscu w mojej tablicy dam liczbe (jesli jest ona taka jak napisalem) wieksza od 2 to juz nie wyswietla mi mozliwosci np. tylko z 3 na poczatku ale tez wyswietla pod koniec kilka z 4 na poczatku i nie potrafie zapisac tej permutacji inaczej zeby wyswietlalo prawidlo. Prosze bardzo o pomoc.

Pozostało 580 znaków

fdsfds
2007-01-14 11:52
fdsfds
0

Eee. Nie chce mi się czytać Twojego kodu... Chciałem tylko napomknąć, że zawsze możesz użyć next_permutation z STLa.

http://www.cppreference.com/cppalgorithm/next_permutation.html

Pozostało 580 znaków

2007-01-16 11:27

Rejestracja: 13 lat temu

Ostatnio: 1 godzina temu

0

No niby tak ale ja bym wolal jaks funkcje w ktorej moge tablice przekazac i takowa otrzymac bo tutaj nie widze takiej mozliwosci.

Pozostało 580 znaków

2007-01-16 16:26

Rejestracja: 13 lat temu

Ostatnio: 10 lat temu

0
next_permutation(tablica, tablica+wielkosc);

A jak chcesz mieć kilka kopii z różnymi permutacjami to co za problem skopiować tablicą przed każdym wywołaniem next_permutation?


but there's no sense crying over every mistake
you just keep on trying till you run out of cake

Pozostało 580 znaków

2007-01-17 00:05

Rejestracja: 13 lat temu

Ostatnio: 1 godzina temu

0

Niby wpisuje tak jak mowisz, ale mam w tablicy liczby 1,2,3,4,5 i jak je permutuje to takie cuda wychodza jakies liczby po przecinku ze sam nie wiem. Moze mi pomozecie.
I ta permutacja niby dziala tylko ja chcialem zeby wyswietlalo tylko te permutacje ktore maja na poczatku te liczbe ktora sobie wybralem. I robie to tak ze daje na poczatek tablicy ta liczbe i potem powtarzam to next permutation albo moja permutacje w petli for silni(m)/(m-1) razy (silnia to funkcja liczaca silnie czyli ilosc wszystkich permutacji). I ja mam w tablicy liczby 1,2,3,4,5 ale to dziala poprawnie tylko dla 1 i 2 a potem wyswietla przez chwile te permutacje z moja liczba na poczatku ale na koniec daje z inna np. dla 5 na poczatku potem wyswietla z jedynka. No i co wy na to?

Pozostało 580 znaków

2007-01-17 10:52

Rejestracja: 13 lat temu

Ostatnio: 10 lat temu

0

Zrobiłem to na vectorach bo mi się nie chciało na tablicach (ale jak ci na tym zależy powinno ci się to spokojnie przerobić tak by było z tablicami)

    vector<int> vect;

    for(int i=1; i<6; i++)
        vect.push_back(i);

    vector< vector<int> > all;

    next_permutation(vect.begin(), vect.end());
    vector<int> backup = vect;

    int liczba;
    cin >> liczba;
    do
    {
        if(vect[0] == liczba)
            all.push_back(vect);
        next_permutation(vect.begin(), vect.end());
    } while(vect != backup);

    for(vector< vector<int> >::iterator it = all.begin(); it < all.end(); it++)
    {
        for(vector<int>::iterator subit = (*it).begin(); subit < (*it).end(); subit++)
            cout << *subit << ' ';
        cout << endl;
    }

but there's no sense crying over every mistake
you just keep on trying till you run out of cake

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0