0197 - Combinari
De la Universitas MediaWiki
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
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")