Sorumluluk Reddi: Aşağıda açıklanan yöntem evrensel değildir ancak genellikle bir sorunu çözebilir veya doğru çözüme ulaşmanıza yardımcı olabilir.
Bir problemde bir permütasyonun varlığını kontrol etmeniz veya eşleşen permütasyonların sayısını veya benzer bir şeyi bulmanız gerekiyorsa, dinamik altküme programlamayı kullanmayı düşünmelisiniz.
Ana parametre, hangi öğelerin permütasyona dahil edildiğini ve hangilerinin edilmediğini gösteren bir bit maskesi olacaktır. Ayrıca, en son hangi öğenin dahil edildiğini gösteren ikinci bir parametre de sıklıkla gereklidir.
Genellikle permütasyonlar, grafiklerdeki yollar bağlamında görülebilir. Buna göre, klasik bir örnek olan Hamilton yol problemini ele alalım.
Bir Hamilton yolu, grafiğin her köşesinden tam olarak bir kez geçen basit bir yoldur. Basitçe, n'nin köşe sayısı olduğu n uzunluğunun bir permütasyonu olarak temsil edilebilir. Bu permütasyon içindeki sıra, bu yoldaki köşelerin geçildiği sırayı gösterecektir.
Grafikte bir Hamilton yolunun varlığını kontrol etmek için dp[mask][son] dinamiklerini başlatalım - maske bit maskesinde birlerle işaretlenmiş köşeleri atlayan ve son köşede sona eren basit bir yol var mı?
İlk değerler dp[2i][i] = true, geri kalanı false olacaktır, bu da her zaman köşelerden herhangi birinde başlayan boş bir yol olduğu anlamına gelir.
dp[mask][last] içinde true değerine sahip olmak, "yolu genişletmek" anlamında ileriye doğru geçişler yapacağız. Yani, maskede sıfır ile işaretlenmiş köşelerin sayısını arayacağız (yolda henüz ziyaret etmedik) ve aynı zamanda sondan bu köşeye bir kenar olacak şekilde (yol olmalıdır) mevcut bir kenar tarafından uzatılabilir). Yani dp[mask | 2k][k] = true if dp[mask][last] = true AND mask & 2k = 0 (k köşesi henüz ziyaret edilmedi) Ve sonunda bir kenar var -> k.
Nihayetinde, hepsi-birler bit maskesinin parametreleri ve herhangi bir son tepe noktası için dp'de gerçek bir değer varsa, bir Hamilton yolu vardır.