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

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()