3150 - permutari pfp

Cerința

Se citește un număr natural n (n<16). Afișați în ordine lexicografică toate permutările mulțimii {1,2,…,n} în care elementele pare sunt puncte fixe (nu își schimbă poziția).

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.

Restricții și precizări

• 1 < n < 16

Exemplul 1

Intrare

5

Ieșire

1 2 3 4 5 
1 2 5 4 3 
3 2 1 4 5 
3 2 5 4 1 
5 2 1 4 3 
5 2 3 4 1

Exemplul 2

Intrare

19

consola

Valoarea lui n nu respectă restricțiile.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii_n(n):

   return 1 < n < 16

def are_elementele_pare_pe_pozitii_corecte(perm):

   for i in range(len(perm)):
       if perm[i] % 2 == 0 and perm[i] != i + 1:
           return False
   return True

def backtracking(perm, poz, n):

   if poz == n:
       if are_elementele_pare_pe_pozitii_corecte(perm):
           print(*perm)
       return
   
   for i in range(1, n + 1):
       if i not in perm:
           perm[poz] = i
           backtracking(perm, poz + 1, n)
           perm[poz] = 0

1. Citirea valorii lui n de la tastatură

n = int(input("Introduceți un număr natural n (1 < n < 16): "))

1. Verificăm restricțiile asupra valorii lui n

if verifica_restrictii_n(n):

   # Inițializarea permutării
   permutare = [0] * n

   # Apelarea funcției pentru a afișa permutările cerute
   backtracking(permutare, 0, n)

else:

   print("Valoarea lui n nu respectă restricțiile.")

</syntaxhighlight>