Generare Combinări

Aspecte teoretice:

În matematică, o combinare reprezintă un mod de a alege dintre elementele unei mulțimi, așa încât (spre deosebire de permutări) ordinea alegerii nu contează, sau mai degrabă numărul total de combinații care pot fi făcute înainte ca una dintre acestea să se repete. În cazurile in care nu sunt multe elemente este posibil să numărăm toate combinările prin scrierea acestora. De exemplu, fiind date trei fructe (un măr, o portocală și o pară), există trei combinări a câte două fructe care pot fi extrase din acest set: un măr și o pară, un măr și o portocală, sau o pară și o portocală. Din punct de vedere formal, o k-combinare a unei mulțimi S este o submulțime de k elemente distincte ale lui S. Dacă această mulțime are n elemente, numărul k-combinărilor este egal cu coeficientul binomial.

Problemă:

Într-un liceu există doar doi profesori de informatică care trebuie să-și împartă cele n clase
care studiază matematica. Știind că primul profesor va trebui să aleagă m (m≤n) din cele n clase pentru a preda matematica la ele, să se afișeze toate combinațiile posibile pentru ambii profesori.
Practic, dacă primul profesor își alege m din cele n clase, cel de al doilea le va lua pe celelalte n-m, deoarece nu se poate ca doi profesori să predea la aceeași clasă. De asemenea, să observăm că nu contează ordinea în care primul profesor alege clasele, de aceea problema se reduce la a genera combinările de n elemente luate câte m.

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace CombinariCS
{
    class Program
    {
        static void ScrieSol(int n, int [] x)
        {
            int i;
            for (i = 1; i <= n; i++)
            {
                Console.Write(x[i] + " ");
            }
            Console.WriteLine();
        }
 
        static void Main(string[] args)
        {
            bool buna;
            int k, m, n;
            int[] x = new int[100];
            Console.Write("Combinari de m: ");
            m = Convert.ToInt32(Console.ReadLine());
            Console.Write("Luate cate n: ");
            n = Convert.ToInt32(Console.ReadLine());
            x[0] = 0;
            k = 1;
            x[k] = 0;
            while (k > 0)
            {
                buna = false;
                while (!buna && x[k] < (m - (n - k)))
                {
                    x[k] = x[k] + 1;
                    buna = true;
                }
                if (buna)
                {
                    if (k == n)
                    {
                        ScrieSol(n,x);
                    }
                    else
                    {
                        k = k + 1;
                        x[k] = x[k - 1];
                    }
                }
                else
                    k = k - 1;
            }
            Console.ReadLine();
        }
    }
}

Cod Sursa VB

Module Module1
    Dim x(100) As Integer
    Dim k, m, n, i As Integer
 
    Sub ScrieSol()
        For i = 1 To n
            Console.Write(x(i) & " ")
        Next i
        Console.WriteLine()
    End Sub
 
    Sub Main()
        Dim buna As Boolean
        Console.Write("Combinari de m: ")
        m = Convert.ToInt32(Console.ReadLine())
        Console.Write("luate cate n: ")
        n = Convert.ToInt32(Console.ReadLine())
        x(0) = 0
        k = 1
        x(k) = 0
        While k > 0
            buna = False
            While (Not buna And x(k) < (m - (n - k)))
                x(k) = x(k) + 1
                buna = True
            End While
            If (buna) Then
                If (k = n) Then
                    ScrieSol()
                Else
                    k = k + 1
                    x(k) = x(k - 1)
                End If
            Else
                k = k - 1
            End If
        End While
        Console.ReadLine()
    End Sub
 
End Module

Cod Sursa C++

#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int k,x[100],m,n,i;
 
void ScrieSol()
{
      for(i=1;i<=n;i++)
        cout<<x[i]<<" ";
      cout<<endl;
        
}
 
int main()
{
    int buna;
    cout<<"Combinari de m: ";cin>>m;
    cout<<"\nluate cate n: ";cin>>n;
    x[0]=0;
    k=1; x[k]=0;   
    while(k>0)
    {
         buna=0;
         while (!buna && x[k] < (m-(n-k) )) 
         {
             x[k]=x[k]+1;                   
             buna=1;
         }
         if (buna) 
             if(k==n) ScrieSol();                     
             else
                {
                   k++;
                   x[k]=x[k-1];
                }
         else
            k--;                     
    }
    system("pause");
}
 

Rezultat: