1278 - ProdusCartezian2

Cerinţa

Se dau n mulțimi:

• A1={1,2,...,v1}
• A2={1,2,...,v2}
• ..
• An={1,2,...,vn}

Să se genereze în ordine lexicografică elementele produsului cartezian .

Date de intrare

Fișierul de intrare produscartezian2IN.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule v[1] v[2] ... v[n].

Date de ieşire

Fișierul de ieșire produscartezian2OUt.txt va conține elementele produsului cartezian, fiecare pe o linie. Valorile de pe fiecare linie vor fi separate prin câte un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricţii şi precizări

• 1 ≤ n ≤ 7
• 1 ≤ v[i] ≤ 7

Exemplul 1:

produscartezian2IN.txt

3
2 1 3

produscartezian2OUT.txt

1 1 1 
1 1 2 
1 1 3 
2 1 1 
2 1 2 
2 1 3 

Exemplul 2:

produscartezian2IN.txt

10
2 1 3

produscartezian2OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def citire():
    with open("produscartezian2IN.txt", "r") as fin:
        n = int(fin.readline().strip())
        v = list(map(int, fin.readline().strip().split()))
    return n, v

def afisare(x, fout):
    fout.write(" ".join(map(str, x)) + '\n')

def backtracking(k, n, v, x, fout):
    if k > n:
        afisare(x, fout)
    else:
        for i in range(1, v[k-1] + 1):
            x[k-1] = i
            backtracking(k + 1, n, v, x, fout)

def verifica_restrictii(n, v):
    if 1 <= n <= 7 and all(1 <= vi <= 7 for vi in v):
        return True
    return False

def main():
    n, v = citire()
    with open("produscartezian2OUT.txt", "w") as fout:
        if verifica_restrictii(n, v):
            x = [0] * n
            backtracking(1, n, v, x, fout)
        else:
            fout.write("Datele nu corespund restrictiilor impuse\n")

if __name__ == "__main__":
    main()