Permütasyonları Üretmek

#Nasıl çalışır?

Bir permütasyon, elemanların bir sıralamasıdır. n farklı elemanın n! (n faktöriyel) permütasyonu vardır: ilk konum için n, ikinci için n − 1 seçenek vb.

Geri izlemeyle her konum için henüz kullanılmamış bir eleman seçilir, kullanıldı olarak işaretlenir ve bir sonraki konuma geçilir. Tüm konumlar dolunca bir permütasyon kaydedilir. Dönüşte seçim geri alınır ve aynı konum için sıradaki eleman denenir.

Arama ağacının ilk seviyesinde n, ikincisinde n · (n − 1) düğüm vardır; yaprak sayısı n!'dir. Elemanlar küçükten büyüğe denenirse permütasyonlar sözlük (leksikografik) sırasıyla üretilir.

#Kendin dene

#Adım adım

1. 01Seçilenler listesi boş, hiçbir eleman kullanılmamış.
2. 02Kullanılmamış her eleman için: elemanı seç, kullanıldı olarak işaretle ve bir sonraki konuma geç.
3. 03Tüm konumlar dolduysa permütasyonu kaydet.
4. 04Dönüşte elemanın seçimini ve işaretini geri al (geri izleme).

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def permutations(items: list) -> list:
    out, chosen, used = [], [], [False] * len(items)

    def visit() -> None:
        if len(chosen) == len(items):
            out.append(list(chosen))
            return
        for i, x in enumerate(items):
            if used[i]:
                continue
            used[i] = True
            chosen.append(x)
            visit()
            chosen.pop()     # undo the choice (backtrack)
            used[i] = False

    visit()
    return out


for p in permutations([1, 2, 3]):
    print(" ".join(map(str, p)))

#Karmaşıklık

n! çok hızlı büyür: 10 eleman 3,6 milyon, 13 eleman 6 milyardan fazla permütasyon demektir. Bu yüzden tüm permütasyonları denemek yalnızca küçük n için uygundur; daha büyük problemlerde budama, DP ya da sezgisel yöntemler gerekir.

#Ne zaman kullanılır?

Küçük boyutlu sıralama problemlerinde kaba kuvvet aramaları (ör. birkaç şehirlik Gezgin Satıcı), anagram üretme, test senaryolarının tüm sıralarını denemek ve bulmaca çözücüler permütasyon üretir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.