Rus Marius: Pagină nouă: = 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`...

2024-01-07T10:21:07Z

Pagină nouă: = 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>...

New page

= 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>

0205 - Shuffle - Revision history