1330 - ParitiiMultime

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 intrare partitiimultimeIN.txt conține pe prima linie numărul n.

Date de ieșire

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

Restricții și precizări

• 1 ≤ n ≤ 9
• Partițiile determinate se vor afișa în ordine lexicografică

Exemplul 1:

partitiimultimeIN.txt

3

partitiimultimeOUT.txt

123*
12*3*
13*2*
1*23*
1*2*3*

Explicație

Sunt determinate 5 partiții distincte ale mulțimii A.

1. {1,2,3}
2. {1,2} U {3}
3. {1,3} U {2}
4. {1} U {2,3}
5. {1} U {2} U {3}

Exemplul 2:

partitiimultimeIN.txt

10

partitiimultimeOUT.txt

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>