Editing 3152 - combinari2


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

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>m</code>.

= 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 =

* <code>1 ≤ m < n ≤ 20</code>

= 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 <code>2</code> și <code>4</code> 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>