Permutacje

    -- Sebastian Pawlak, 1999.


Permutacja jest to wzajemne jednoznaczne przekształcenie pewnego zbioru na siebie. Jeśli dany zbiór ma "n" elementów, to liczba permutacji (różnych szeregów zbudowanych z elementów danego zbioru) wynosi n!. Przedstawiony algorytm Dijkstry, dla zadanego zbioru liczb generuje "następnik permutacyjny". Np. dla zbioru trzech liczb 1, 2, 3 na wyjściu pojawi się 1, 3, 2. Gdy otrzymany zbiór 1, 3, 2 podamy na wejście to otrzymamy 2, 1, 3 i następnie: 2, 3, 1; 3, 1, 2 i ostatni 3, 2, 1.

Algorytm postępowania przy wyznaczaniu permutacji danego szeregu liczb:

Załóżmy, że mamy dany szereg: 1 4 6 2 9 5 8 7 3. Oto w jaki sposób wyznacza się jego następnik:

1. Poruszamy się od prawej strony do lewej, tak długo aż napotkamy element
   mniejszy od swojego prawego sąsiada. W tym przypadku elementem tym będzie
   5 o ideksie i=5 (liczonym od zera);

2. Poruszając się ponownie od prawej strony szukamy pierwszego elementu
   większego niż ten znaleziony na pozycji "i", czyli 5. Elementem tym będzie
   7 o indeksie j=7.

3. Zamieniamy miejscami elementy o indeksach "i" oraz "j". Otrzymamy szereg:
   1 4 6 2 9 7 8 5 3.

4. Odbijamy lustrzanie szereg elementów od indeksu i+1 do końca szeregu.
   Otrzymamy szereg: 1 4 6 2 9 7 3 5 8. Wyznaczony szereg jest szukanym
   przez nas rozwiązaniem.

Oto jak zaimplementowałem powyższy algorytm:


Kod źródłowy pliku "permutacje.c":

/* Permutacje, algorytm Dijkstry 
 * Sebastian Pawlak, 1999
 */
#include <stdio.h>

void permutacja(int t[], int max);
void wypisz(int t[], int max);

int main(void)
{
    #define MAX 3
    int t[MAX] = { 1, 2, 3 };
    int i, j;

    wypisz(t, MAX);
    for (i = 0; i < 1 * 2 * 3 - 1; i++) {  /* i < n! - 1 */
        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');
}
w3cw3c
automatyka przemysłowa