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

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

# Citirea valorii lui n de la tastatură
n = int(input("Introduceți un număr natural n (1 < n < 16): "))

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