Permütasyonlar

Geri İzleme O(n · n!) O(n)

Her konumu sırayla sabitleyip takas ederek, sonra takası geri alarak bir kümenin tüm sıralamalarını üretir.

oluşturuluyor

[123]

kaydedilen (0)

henüz yok

Elemanlar: 1, 2, 3 · 0 / 6 bulundu

1/36

0. konum sabitleniyor = 1.

Değişmez0..k-1 konumları sabittir; geri kalan, henüz kullanılmamış değerlerin bir permütasyonudur.

seçgeri izlemekaydedildi

permutations.c

void permute(int a[], int n, int k) {
    if (k == n) {
        printPerm(a, n);
        return;
    }
    for (int i = k; i < n; i++) {
        swap(&a[k], &a[i]);
        permute(a, n, k + 1);
        swap(&a[k], &a[i]);   /* undo */
    }
}

Permütasyonlar nasıl çalışır?

Her adayı takasla ilk konuma sabitle, kalanında özyinele, sonra takası geri al. Geri alma diziyi dallar arasında yeniden kullanılabilir tutar.

Ne zaman kullanılır?

Sıralamaları sayma: kaba kuvvet TSP, anagram üretimi, test durumu karıştırma.