0202 - PermPF
De la Universitas MediaWiki
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
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)
# 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.")