3152 - combinari2

Cerința

Se citesc două numere naturale n și m. Afișați în ordine lexicografică toate submulțimile cu m elemente ale mulțimii {1, 2, ..., n} în care nu există două elemente pare alăturate.

Date de intrare

Programul citește de la tastatură numerele n și m.

Date de ieșire

Programul va afișa pe ecran submulțimile cerute, câte una pe fiecare rand și având elementele separate prin câte un spaţiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricții și precizări

• 1 ≤ m < n ≤ 20

Exemplul 1

Intrare

5 3

Ieșire

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

Explicație

Numrele 2 și 4 nu apar pe poziții alăturate.

Exemplul 2

Intrare

22 17

consola

Nu corespunde restricțiilor

Rezolvare

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

   return 1 <= m < n <= 20

def este_submultime_valida(submultime):

   for i in range(len(submultime) - 1):
       if submultime[i] % 2 == 0 and submultime[i + 1] % 2 == 0:
           return False
   return True

def genereaza_submultimi(n, m, submultime_curenta, index):

   if len(submultime_curenta) == m:
       if este_submultime_valida(submultime_curenta):
           print(*submultime_curenta)
       return

   if index > n:
       return

   # Include elementul la index în submulțime
   genereaza_submultimi(n, m, submultime_curenta + [index], index + 1)

   # Sări peste elementul la index
   genereaza_submultimi(n, m, submultime_curenta, index + 1)

if __name__ == "__main__":

   n, m = map(int, input("Introduceți valorile pentru n și m (separate prin spațiu): ").split())

   if not este_input_valid(n, m):
       print("Nu corespunde restricțiilor")
   else:
       print(f"Submulțimile cu {m} elemente ale mulțimii {{1, 2, ..., {n}}} în care nu există două elemente pare alăturate sunt:")
       genereaza_submultimi(n, m, [], 1)

</syntaxhighlight>