3689 - 2gen

Cerința

Se n și m numere naturale. Afișați în ordine lexicografică toate șirurile de lungime m care conțin numere de la 1 la n și fiecare valoare apare de maxim două ori.

Date de intrare

Fișierul de intrare 2genIN.txt conține pe prima linie numerele n și m separate prin spațiu.

Date de ieșire

Fișierul de ieșire 2genOUT.txt va conține câte o soluție pe linie. Numerele de pe aceeași linie se separă prin spații. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricții și precizări

• 1 ≤ n ≤ 6
• 1 ≤ m ≤ 6

Exemplul 1

2genIN.txt

4 3

2genOUT.txt

1 1 2 
1 1 3 
1 1 4 
1 2 1 
1 2 2 
1 2 3 
1 2 4 
1 3 1 
1 3 2 
1 3 3 
1 3 4 
1 4 1 
1 4 2 
1 4 3 
1 4 4 
2 1 1 
2 1 2 
2 1 3 
2 1 4 
2 2 1 
2 2 3 
2 2 4 
2 3 1 
2 3 2 
2 3 3 
2 3 4 
2 4 1 
2 4 2 
2 4 3 
2 4 4 
3 1 1 
3 1 2 
3 1 3 
3 1 4 
3 2 1 
3 2 2 
3 2 3 
3 2 4 
3 3 1 
3 3 2 
3 3 4 
3 4 1 
3 4 2 
3 4 3 
3 4 4 
4 1 1 
4 1 2 
4 1 3 
4 1 4 
4 2 1 
4 2 2 
4 2 3 
4 2 4 
4 3 1 
4 3 2 
4 3 3 
4 3 4 
4 4 1 
4 4 2 
4 4 3 

Exemplul 2

2genIN.txt

7 7 

consola

Nu corespunde restricțiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def genereaza_siruri(n, m):

   def backtracking(sir_partial):
       if len(sir_partial) == m:
           solutii.append(sir_partial.copy())
           return

       for numar in range(1, n + 1):
           if folosit[numar] < 2:
               sir_partial.append(numar)
               folosit[numar] += 1

               backtracking(sir_partial)

               sir_partial.pop()
               folosit[numar] -= 1

   solutii = []
   folosit = {numar: 0 for numar in range(1, n + 1)}
   backtracking([])

   return solutii

def main():

   # Citire date de intrare
   with open("2genIN.txt", "r") as fisier_intrare:
       n, m = map(int, fisier_intrare.readline().split())

   # Verificare restricții
   if not (1 <= n <= 6 and 1 <= m <= 6):
       print("Nu corespunde restricțiilor")
       return

   # Generare șiruri
   siruri = genereaza_siruri(n, m)

   # Scriere rezultate în fișierul de ieșire
   with open("2genOUT.txt", "w") as fisier_iesire:
       if siruri:
           for sir in siruri:
               fisier_iesire.write(" ".join(map(str, sir)) + "\n")
       else:
           fisier_iesire.write("Nu corespunde restricțiilor\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>