Oros Ioana Diana: Pagină nouă: = Cerința = Fie `n` un număr natural nenul și mulțimea `A={1,2,3,...,n}`. Să se determine toate partițiile disjuncte ale mulțimii `A`. O partiție a mulțimii `A` este formată din `m` (`1 ≤ m ≤ n`) submulțimi disjuncte ale lui `A`: `A1`, `A2`, …, `Am` cu proprietatea că `A=A1U A2` `U...U Am`. = Date de intrare = Fișierul de int...

2024-05-18T19:44:29Z

Pagină nouă: = Cerința = Fie <code>n</code> un număr natural nenul și mulțimea <code>A={1,2,3,...,n}</code>. Să se determine toate partițiile disjuncte ale mulțimii <code>A</code>. O partiție a mulțimii <code>A</code> este formată din <code>m</code> (<code>1 ≤ m ≤ n</code>) submulțimi disjuncte ale lui <code>A</code>: <code>A1</code>, <code>A2</code>, …, <code>Am</code> cu proprietatea că <code>A=A1U A2</code> <code>U...U Am</code>. = Date de intrare = Fișierul de int...

New page

= Cerința =
Fie <code>n</code> un număr natural nenul și mulțimea <code>A={1,2,3,...,n}</code>. Să se determine toate partițiile disjuncte ale mulțimii <code>A</code>.

O partiție a mulțimii <code>A</code> este formată din <code>m</code> (<code>1 ≤ m ≤ n</code>) submulțimi disjuncte ale lui <code>A</code>: <code>A1</code>, <code>A2</code>, …, <code>Am</code> cu proprietatea că <code>A=A1U A2</code> <code>U...U Am</code>.

= Date de intrare =
Fișierul de intrare <code>partitiimultimeIN.txt</code> conține pe prima linie numărul <code>n</code>.

= Date de ieșire =
Fișierul de ieșire <code>partitiimultimeOUT.txt</code> va conține câte o linie pentru fiecare partiție determinată. Submulțimile vor fi separate în fiecare linie cu ajutorul caracterului <code>*</code>, iar elementele fiecărei submulțimi se vor scrie fără spațiere, ca în exemplul de mai jos.

= Restricții și precizări =

* <code>1 ≤ n ≤ 9</code>
* Partițiile determinate se vor afișa în ordine lexicografică

= Exemplul 1: =
<code>partitiimultimeIN.txt</code>
3
<code>partitiimultimeOUT.txt</code>
123*
12*3*
13*2*
1*23*
1*2*3*

=== Explicație ===
Sunt determinate <code>5</code> partiții distincte ale mulțimii <code>A</code>.

# <code>{1,2,3}</code>
# <code>{1,2} U {3}</code>
# <code>{1,3} U {2}</code>
# <code>{1} U {2,3}</code>
# <code>{1} U {2} U {3}</code>

== Exemplul 2: ==
<code>partitiimultimeIN.txt</code>
10
<code>partitiimultimeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def maxim(k, x):
z = 0
for i in range(1, k):
z = max(x[i], z)
return z

def scrie(x, n, g):
z = maxim(n + 1, x)
for i in range(1, z + 1):
for j in range(1, n + 1):
if x[j] == i:
g.write(str(j))
g.write("*")
g.write("\n")

def back(k, n, x, g):
if k == n + 1:
scrie(x, n, g)
else:
for i in range(1, maxim(k, x) + 2):
x[k] = i
back(k + 1, n, x, g)

def verifica_restrictii(n, g):
if not (1 <= n <= 9):
g.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def main():
with open("partitiimultimeIN.txt", "r") as f:
n = int(f.readline().strip())

with open("partitiimultimeOUT.txt", "w") as g:
if verifica_restrictii(n, g):
x = [0] * (n + 1)
x[1] = 1
back(2, n, x, g)

if __name__ == "__main__":
main()

</syntaxhighlight>

1330 - ParitiiMultime - Revision history