Naszym zadaniem było zaimplementowanie algorytmu do wyszukiwania wszystkich permutacji danego zbioru. Do tego celu skorzystaliśmy z gotowego algorytmu, wspomianiego w prezentacji (cs.princeton.edu/~rs/talks/perms.pdf), implementując go w języku C i przystosowując do współpracy z dynamiczną tablicą danych reprezentującą permutowany zbiór.


#include <stdio.h>
#include <stdlib.h>

int* tab;
int n;

void pokaz() {
    int i;
    for (i = 1; i <= n; ++i) printf("%d", tab[i]);
    puts("");
}

int zamien(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void generuj(int u) {
    int c;
    if (u == 1) {
        pokaz();
        return;
    }
    for (c = 1; c <= u; ++c) {
        zamien(&tab[c], &tab[u]);
        generuj(u-1);
        zamien(&tab[c], &tab[u]);
    }
}

int main(int argc, char** argv) {
    if (argc != 2) {
        printf("Uzycie: %s <pojemnosc>\n", argv[0]);
        return 1;
    }

    n = atoi(argv[1]);
    tab = malloc((n+1)*sizeof(int));
    int i;
    for (i = 1; i <= n; ++i) tab[i] = i;

    generuj(n);

    free(tab);
    return 0;
}

Przykładowe wyjście programu dla n=5
23451
32451
34251
43251
24351
42351
43521
34521
35421
53421
45321
54321
24531
42531
45231
54231
25431
52431
23541
32541
35241
53241
25341
52341
53412
35412
34512
43512
54312
45312
43152
34152
31452
13452
41352
14352
54132
45132
41532
14532
51432
15432
53142
35142
31542
13542
51342
15342
25413
52413
54213
45213
24513
42513
45123
54123
51423
15423
41523
14523
24153
42153
41253
14253
21453
12453
25143
52143
51243
15243
21543
12543
23514
32514
35214
53214
25314
52314
53124
35124
31524
13524
51324
15324
25134
52134
51234
15234
21534
12534
23154
32154
31254
13254
21354
12354
23415
32415
34215
43215
24315
42315
43125
34125
31425
13425
41325
14325
24135
42135
41235
14235
21435
12435
23145
32145
31245
13245
21345
12345


Korzystając z komendy time, wyznaczyliśmy przybliżoną charakterystykę złożoności czasowej algorytmu.
[n]  [s]
1  0.001
2  0.001
3  0.001
4  0.001
5  0.001
6  0.001
7  0.005
8  0.037
9  0.358
10 4.033
11 48.491

[wykresik plosię]


Złożoność tego algorytmu to, jak widać, O(n!). Jest to zupełnie wystarczający wynik dla małych zbiorów danych wejściowych, lecz w przypadku już niewiele większych absolutnie nieakceptowalny. Permutacje stosowane są m. in. do testowania programów (losowy ciąg danych wejściowych użytkownika).