Vizualizare sursă pentru „3988 - permnk”

= Cerința =
Se dau numerele naturale <code>n</code> si <code>k</code>. Sa se genereze in ordine lexicografică toate permutările mulțimii <code>{1,2,...,n}</code> cu proprietatea că diferența în modul dintre oricare două numere alăturate din permutare este de cel mult <code>k</code>.

= Date de intrare =
Programul citește de pe prima linie numărul <code>n</code>, iar de pe a doua linie numărul <code>k</code>.

= Date de ieșire =
Programul va afișa pe ecran, pe câte o linie, în ordine lexicografică, permutările cerute.

= Restricții și precizări =

* <code>1 ≤ k ≤ n ≤ 9</code>

= Exemplul 1 =
Intrare
 4
 2
Ieșire
 1 2 3 4
 1 2 4 3
 1 3 2 4
 1 3 4 2
 2 1 3 4
 2 4 3 1
 3 1 2 4
 3 4 2 1
 4 2 1 3
 4 2 3 1
 4 3 1 2
 4 3 2 1

== Explicație ==
Lipsesc permutările în care <code>1</code> și <code>4</code> sunt alăturate, deoarece diferența lor în modul este mai mare decât <code>2</code>.

== Exemplul 2 ==
Intrare
 5
 7
consola
 Restricții neîndeplinite. Asigurați-vă că 
 1 <= k <= n <= 9.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def este_permutare_valida(permutare, k):
    for i in range(1, len(permutare)):
        if abs(permutare[i] - permutare[i-1]) > k:
            return False
    return True

def genereaza_permutari(n, k, permutare_curenta):
    if len(permutare_curenta) == n:
        if este_permutare_valida(permutare_curenta, k):
            print(" ".join(map(str, permutare_curenta)))
        return

    for numar in range(1, n + 1):
        if numar not in permutare_curenta:
            genereaza_permutari(n, k, permutare_curenta + [numar])

def verifica_restrictii(n, k):
    return 1 <= k <= n <= 9

if __name__ == "__main__":
    n = int(input("Introduceți n: "))
    k = int(input("Introduceți k: "))

    if verifica_restrictii(n, k):
        genereaza_permutari(n, k, [])
    else:
        print("Restricții neîndeplinite. Asigurați-vă că 1 <= k <= n <= 9.")

</syntaxhighlight>