Editing 0205 - Shuffle

= Cerinţa =
Se citeşte un număr natural nenul <code>n</code> şi o permutare a mulţimii <code>M={1,2,..,n}</code>. 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 <code>shuffleIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> valori distincte cuprinse între <code>1</code> și <code>n</code>, separate prin câte un spațiu, reprezentând permutarea dată.

= Date de ieşire =
Fişierul de ieşire <code>shuffleOUT.txt</code> va conţine pe fiecare linie elementele unei permutări, separate prin câte un spaţiu.

= Restricţii şi precizări =

* <code>0 < n < 9</code>
* dacă nu există soluţii se va afişa pe prima linie a fişierului de ieşire mesajul <code>nu exista</code>

= Exemplul 1: =
<code>shuffleIN.txt</code>
 4
 2 3 1 4
<code>shuffleOUT.txt</code>
 1 2 4 3 
 3 4 2 1 

= Exemplul 2: =
<code>shuffleIN.txt</code>
 11
 2 3 1 4
<code>shuffleOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>