3911 - PermPrimPF

Cerința

Se dă o mulțime cu n elemente, numere naturale. Afișați în ordine lexicografică toate permutările mulțimii date în care elementele prime sunt puncte fixe (nu își schimbă poziția).

Date de intrare

Programul citește de la tastatură numărul n și apoi n numere naturale, reprezentând elementele mulțimii.

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 ≤ 15
• numărul valorilor prime din șir va fi aproximativ egal cu cel al valorilor neprime

Exemplu 1

Intrare

5
9 7 1 2 8

Iesire

1 7 8 2 9
1 7 9 2 8
8 7 1 2 9
8 7 9 2 1
9 7 1 2 8
9 7 8 2 1

Rezolvare

import itertools

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def read_input():
    n = int(input().strip())
    elements = list(map(int, input().strip().split()))
    return n, elements

def write_output(permutations):
    for perm in permutations:
        print(" ".join(map(str, perm)))

def generate_permutations(n, elements):
    prime_positions = {i: elements[i] for i in range(n) if is_prime(elements[i])}
    non_prime_elements = [elements[i] for i in range(n) if i not in prime_positions]
    
    non_prime_permutations = itertools.permutations(non_prime_elements)
    
    permutations = []
    for perm in non_prime_permutations:
        perm_list = list(elements)
        perm_iter = iter(perm)
        for i in range(n):
            if i not in prime_positions:
                perm_list[i] = next(perm_iter)
        permutations.append(perm_list)
    
    return sorted(permutations)

def main():
    n, elements = read_input()
    
    if not (1 < n <= 15):
        raise ValueError("n trebuie să fie între 1 și 15")
    
    if not all(isinstance(x, int) and x >= 0 for x in elements):
        raise ValueError("Toate elementele trebuie să fie numere naturale.")
    
    permutations = generate_permutations(n, elements)
    write_output(permutations)

if __name__ == '__main__':
    main()