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

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.")