0202 - PermPF

Enunț

Fie mulţimea M={1,2,..,n} şi P(1),P(2),...,P(n) o permutare a ei. Elementul x din M se numeşte punct fix dacă P(x)=x.

Cerinţa

Se citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările fără puncte fixe ale mulţimii {1,2,..,n}.

Date de intrare

Fişierul de intrare permpfIN.txt conţine pe prima linie numărul n.

Date de ieşire

Fişierul de ieşire permpfOUT.txt va conţine pe fiecare linie elementele unei permutări, separate prin câte un spaţiu.

Restricţii şi precizări

• 0 < n < 9

Exemplul 1

permpfIN.txt

3

permpfOUT.txt

2 3 1 
3 1 2 

Exemplul 2

permpfIN.txt

10

Consola

Valoarea lui n nu respectă restricțiile.

Rezolvare

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

   return 0 < n < 9

def are_puncte_fixe(perm):

   for i in range(len(perm)):
       if perm[i] == i + 1:
           return True
   return False

def backtracking(perm, poz, n, output_file):

   if poz == n:
       if not are_puncte_fixe(perm):
           output_file.write(' '.join(map(str, perm)) + '\n')
       return
   
   for i in range(1, n + 1):
       if i not in perm:
           perm[poz] = i
           backtracking(perm, poz + 1, n, output_file)
           perm[poz] = 0

def permutari_fara_puncte_fixe(n, output_file):

   perm = [0] * n
   backtracking(perm, 0, n, output_file)

1. Citirea valorii lui n din fișierul de intrare

with open("permpfIN.txt", "r") as input_file:

   line = input_file.readline().strip()
   if not line:
       print("Fișierul de intrare este gol sau corupt.")
   else:
       try:
           n = int(line)
           # Verificăm restricțiile asupra valorii lui n
           if verifica_restrictii_n(n):
               # Deschiderea fișierului de ieșire
               with open("permpfOUT.txt", "w") as output_file:
                   # Apelăm funcția pentru generarea permutărilor fără puncte fixe
                   permutari_fara_puncte_fixe(n, output_file)
           else:
               print("Valoarea lui n nu respectă restricțiile.")
       except ValueError:
           print("Linia citită din fișier nu reprezintă un număr întreg valid.")

</syntaxhighlight>