3988 - permnk

Cerința

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

Date de intrare

Programul citește de pe prima linie numărul n, iar de pe a doua linie numărul k.

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

• 1 ≤ k ≤ n ≤ 9

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 1 și 4 sunt alăturate, deoarece diferența lor în modul este mai mare decât 2.

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>