3988 - permnk
De la Universitas MediaWiki
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
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.")