0197 - Combinari

Cerinţa

Se citesc două numere naturale nenule n și k. Să se afişeze, în ordine lexicografică, submulțimile de câte k elemente ale mulţimii {1,2,..,n}.

Date de intrare

Fişierul de intrare combinariIN.txt conţine pe prima linie numerele n și k, separate printr-un spatiu.

Date de ieşire

Fişierul de ieşire combinariOUT.txt va conţine pe fiecare linie câte k valori, separate prin câte un spaţiu, reprezentând elementele unei submulțimi.

Restricţii şi precizări

• 1 ≤ k ≤ n ≤ 15
• elementele fiecărei submulţimi vor fi afişate în ordine crescătoare

Exemplul 1

combinariIN.txt

4 2

combinariOUT.txt

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

Exemplul 2

combinariIN.txt

4 2

consola

"Nu corespunde restricțiilor"

Rezolvare

<syntaxhighlight lang="python3" line="1"> def generate_combinations(n, k, current_combination, start, result):

   if k == 0:
       result.append(current_combination[:])
       return

   for i in range(start, n + 1):
       current_combination.append(i)
       generate_combinations(n, k - 1, current_combination, i + 1, result)
       current_combination.pop()

def generate_and_write_combinations(input_file, output_file):

   try:
       with open(input_file, 'r') as file:
           n, k = map(int, file.readline().split())

       if not (1 <= k <= n <= 15):
           raise ValueError("Nu corespunde restricțiilor")

       result = []
       generate_combinations(n, k, [], 1, result)

       with open(output_file, 'w') as file:
           for combination in result:
               file.write(' '.join(map(str, combination)) + '\n')
   except ValueError as e:
       with open(output_file, 'w') as file:
           file.write(str(e) + '\n')

if __name__ == "__main__":

   generate_and_write_combinations("combinariIN.txt", "combinariOUT.txt")

</syntaxhighlight>