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

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