0205 - Shuffle

Cerinţa

Se citeşte un număr natural nenul n şi o permutare a mulţimii M={1,2,..,n}. Să se afişeze, în ordine lexicografică, toate permutările mulţimii M care nu conţin elemente alăturate care au fost alăturate şi în permutarea dată.

Date de intrare

Fişierul de intrare shuffleIN.txt conţine pe prima linie numărul n, iar pe a doua linie n valori distincte cuprinse între 1 și n, separate prin câte un spațiu, reprezentând permutarea dată.

Date de ieşire

Fişierul de ieşire shuffleOUT.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
• dacă nu există soluţii se va afişa pe prima linie a fişierului de ieşire mesajul nu exista

Exemplul 1:

shuffleIN.txt

4
2 3 1 4

shuffleOUT.txt

1 2 4 3 
3 4 2 1 

Exemplul 2:

shuffleIN.txt

11
2 3 1 4

shuffleOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def citire():
    with open("shuffleIN.txt", "r") as input_file:
        n = int(input_file.readline().strip())
        v = [0] + list(map(int, input_file.readline().split()))
    return n, v

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

def sortare(n, v):
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            if not prim(v[i]) and not prim(v[j]) and v[i] > v[j]:
                v[i], v[j] = v[j], v[i]

def puncte_fixe(n, v):
    x = [0] * (n + 1)
    for i in range(1, n + 1):
        if prim(v[i]):
            x[i] = i
    return x

def afisare(n, v, x, output_file):
    result = [v[x[i]] for i in range(1, n + 1) if x[i] != 0]
    output_file.write(" ".join(map(str, result)) + "\n")

def valid(k, x):
    for i in range(1, k):
        if x[i] == x[k]:
            return False
    return True

def backtracking(k, n, v, x, output_file):
    if k > n:
        afisare(n, v, x, output_file)
    else:
        if prim(v[k]):
            backtracking(k + 1, n, v, x, output_file)
        else:
            for i in range(1, n + 1):
                if not prim(v[i]):
                    x[k] = i
                    if valid(k, x):
                        backtracking(k + 1, n, v, x, output_file)

def verifica_restrictii(n):
    if 0 < n < 9:
        return True
    else:
        with open("shuffleOUT.txt", "w") as output_file:
            output_file.write("Datele nu corespund restrictiilor impuse\n")
        return False

def main():
    n, v = citire()

    if verifica_restrictii(n):
        sortare(n, v)
        x = puncte_fixe(n, v)

        with open("shuffleOUT.txt", "w") as output_file:
            backtracking(1, n, v, x, output_file)

if __name__ == "__main__":
    main()