Programozás‎ > ‎Feladatok‎ > ‎

Langford permutációk

Adottak az {1, 1, 2, 2, …, n, n} számok. Van-e olyan sorrendjük, ahol a k szám két előfordulása között pontosan k darab elem van, minden ∈ {1,2,…,n} esetén? 

Ha igen, adjunk meg egy ilyen permutációt! Adott 1 <= n <= 16 esetén adjuk meg, hány különböző Langford permutáció létezik.

Példa

Ha = 3, akkor egyetlen ilyen permutáció létezik: 231213.
Megjegyzés: a szimmetrikus párokat azonosnak tekintjük, tehát a 312132 ugyanannak számít, mint a fenti megoldás.

Tesztadatok

L[n] a Langford-permutációk számát jelöli.

 nL[n]
 1 0
 2 0
 3 1
 4 1
 5 0
 6 0
 7 26
 8 150
 9 0
 10 0
 11 17792
 12 108144
 13 0
 14 0
 15 39809640
 16 326721800

Címkék

A feladat forrása: saját feladat
Algoritmusok: összes eset generálása, visszalépéses keresés, backtrack

megoldás