[C] Algoritmo combinazioni crescenti

[dan952]

Mi servirebbe una mano per implementare un algoritmo che dato in input tre numeri $n$, $k$ e $m \geq 0$ mi restituisca m-esima combinazione crescente di n numeri di classe k.


Es. n=6, k=3 e m=11 deve restituire 2 3 5
Infatti:
123
124
125
126
134
135
136
145
146
156
234
235

[vict85]

Se un algoritmo di complessità \(\displaystyle O(mk) \) ti è sufficiente allora ti basta generare tutti gli elementi in ordine fino a \(\displaystyle m \). Insomma il punto fondamentale è l'implementazione della funzione prossima_combinazione. Immagino si possa fare di meglio ma richiede di fare molti calcoli preliminari.

[dan952]

Sì così lo avevo già fatto, ma il prof. ha dato un suggerimento di cercare la combinazione dividendo in range, mi spiego meglio, le combinazioni che iniziano con 1 vanno da 0 al $((n-1),(k-1))-1$, quelle che cominciano con 2 da $((n-1),(k-1))$ a $((n-1),(k-1))+((n-2),(k-1))-1$, ecc...ma il problema è che non ho ben capito come procedere.

[Super Squirrel]

Ho provato a farlo, sembra funzionare.
Ho messo che gli n numeri partono da 0 e arrivano a n-1. Nel caso gli n numeri vanno inseriti manualmente basta fare qualche piccola modifica.
Ecco il codice se ti può essere utile:

#include <iostream>
#include <cstdint>

int64_t fattoriale(int x)
{
    int64_t fatt = 1;
    if(x == 0 || x == 1)
    {
        return fatt;
    }
    while(x > 1)
    {
        fatt = fatt * x;
        x--;
    }
    return fatt;
}

int64_t combinazioni(int n, int k)
{
    int64_t comb;
    comb = fattoriale(n) / ( fattoriale(n - k) * fattoriale(k) );
    return comb;
}

int main()
{
    int n, k, m, v[50];
    std::cout << "n:";
    std::cin >> n;
    std::cout << "k(minore o uguale di " << n << "):";
    std::cin >> k;
    std::cout << "m(compreso tra 1 e " << combinazioni(n, k) << "):";
    std::cin >> m;
    for(int i = 0; i < k; i++)
    {
        v[i] = i;
    }
    while(m > 1)
    {
        for(int i = k - 1; i >= 0; i--)
        {
            if(v[i] < n - k + i)
            {
                v[i]++;
                if(i != k - 1)
                {
                    for(int j = i + 1; j < k; j++)
                    {
                        if(v[j - 1] < n - k + j - 1)
                        {
                            v[j] = v[j - 1] + 1;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                break;
            }
        }
        m--;
    }
    for(int i = 0; i < k; i++)
    {
        std::cout << v[i] << "\t";
    }
}

[dan952]

Ti ringrazio molto dell'impegno ma se calcoli esplicitamente $n!$ ammazzi il computer già per $n$ abbastanza piccoli, per calcolare il binomiale basta fare la funzione ricorsiva:

Int bin(n,k){
        if (n==k or k==0) return 1;
        else return bin(n-1,k)+bin(n-1,k-1);
}

[dan952]

Per chi fosse interessato all'esercizio lo posto, dopo svariati sforzi, eccolo:

#include <stdio.h>
int bin(int n,int k){
    if (n==k or k==0) return 1;
    return bin(n-1,k)+bin(n-1,k-1);
}
void comb(int n, int k, int m){
    int cont=0,sum,sum_1,i,j,k_1;
    k_1=k;
    for (i=1;i<=k;i++){
        sum=0;
        for(j=n-1;j>=k_1-1;j--){
            sum_1=sum;
            cont=cont+1;
            sum=sum+bin(j,k_1-1);
            if (m<sum){
                printf("%d ",cont);
                m=m-sum_1;
                n=j;
                k_1=k_1-1;
                j=k_1-2;
                
            }
        }
    }
    
   
}


int main(){

    int n,k,m;
    scanf("%d",&n);
    scanf("%d",&k);
    scanf("%d",&m);
    comb(n,k,m);
    
    return 1;
}

Adesso non so però come salvarlo in formato .c dato che me lo salva solo in .cpp

[vict85]

Con che standard C stai lavorando e su che compilatore?

I modi che usate per calcolare i binomiali sono pessimi: quello di SuperSquirrel rischia l'overflow (è sufficiente porre \(n>20\)). Al contrario quello di dan95 ha il problema di ricalcolare molte cose più volte (quindi ha una complessità troppo alta).

In ogni caso il metodo di SuperSquirrel può essere migliorato, seppur il rischio di overflow sia inevitabile. Io proporrei questa versione (scritta in C++11), ma può essere facilmente riscritta in C99/C11. Questa versione cerca di ridurre sia la crescita dei valori considerati che il numero di calcoli.

#include <cstdint>
#include <iostream>
 
using std::uint32_t; // mi permette di fare a meno di scrivere il namespace
 
constexpr uint64_t binom(uint32_t n, uint32_t k)
{
	if(k > n)
		return 0;
    if(n == 0 || k == 0 || n == k)
        return 1;
    auto bin = uint64_t{ 1 };
    auto max = k > n - k ? n : n -k;
    for(auto i = n; i > max; --i)
    {
        bin *= i;
        bin /= (n-i+1); 
    }
 
    return bin;
}

una versione ancora più "sicura" (al costo di qualche calcolo in più) è la seguente:

#include <cstdint>
#include <iostream>
 
using std::uint32_t; // mi permette di fare a meno di scrivere il namespace
 
constexpr uint64_t binom(uint32_t n, uint32_t k)
{
	if(k > n)
		return 0;
    if(n == 0 || k == 0 || n == k)
        return 1;
    auto bin = uint64_t{ 1 };
    auto max = k > n - k ? n : n -k;
    for(uint64_t i = n, j = 1; i != max; --i, ++j)
    {
    	auto temp = i;
        if(bin % j == 0)
            bin /= j;
        else
            temp /= j;
        bin *= temp;
    }
 
    return bin;
}

[Super Squirrel]

@vict85
Purtroppo conoscendo solo le basi del C++ non riesco a capire molte parti del codice. Ha un nome questo metodo oppure potresti dirmi in soldoni cosa fa?

Comunque nel codice che ho postato in precedenza mi sono concentrato sulla funzione "prossima_combinazione", ovviamente la funzione che calcola il numero di combinazioni è ampiamente migliorabile (causa overflow)... la prima cosa che mi viene in mente è per esempio la semplificazione di un rapporto di fattoriali.

In ogni caso il numero di combinazioni nel mio programma veniva calcolato solo per avvisare in output del range in cui doveva ricadere m. Ragionando un po' ho modificato il programma evitando il calcolo dei binomiali, in pratica inserisci m (senza che venga data nessuna informazione sul massimo valore che può assumere) e senza pericoli di overflow il programma ti restituisce l'm-esima combinazione se m è minore del numero di combinazioni o il numero di combinazioni se m è maggiore.
Non ho praticamente nessuna conoscenza riguardo alla complessità di un algoritmo e cose simili, ma mi sembra che questo codice (magari poi è probabile che ci sia qualche errore) sia molto più veloce di quello postato da dan95.

#include <iostream>

int main()
{
    int n, k, m, v[100], comb = 1;
    bool a = 1;
    std::cout << "n(maggiore di 0):";
    std::cin >> n;
    std::cout << "k(compreso tra 1 e " << n << "):";
    std::cin >> k;
    std::cout << "m:";
    std::cin >> m;
    for(int i = 0; i < k; i++)
    {
        v[i] = i;
    }
    while(m > 1)
    {
        a = 0;
        for(int i = k - 1; i > - 1; i--)
        {
            if(v[i] < n - k + i)
            {
                v[i]++;
                comb++;
                a = 1;
                if(i != k - 1)
                {
                    for(int j = i + 1; j < k; j++)
                    {
                        if(v[j - 1] < n - k + j - 1)
                        {
                            v[j] = v[j - 1] + 1;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                break;
            }
        }
        if(a == 0)
        {
            break;
        }
        m--;
    }
    if(a == 0)
    {
        std::cout << "m > C(n,k) = " << comb;
    }
    else
    {
        for(int i = 0; i < k; i++)
        {
            std::cout << v[i] << "\t";
        }
    }
}

[vict85]

Ho solo usato il fatto che \(\displaystyle \binom{n}{k} = \binom{n}{k-1}\cdot\frac{n-k+1}{k}\) e fatto dei semplici ragionamenti sui divisori.

Il codice non è difficile con delle basi del C++. Il constexpr puoi ignorarlo[nota]È un invito al compilatore di calcolare il risultato della funzione in fase di compilazione ogni qual volta i coefficienti siano conosciuti in fase di compilazione.[/nota], auto invece seleziona in automatico il tipo della variabile.

[dan952]

Conosco il C standard.

Usando la formula di vict per il calcolo del binomiale:

int bin(int n, int k){
    
    if (n==k or k==0) return 1;
    
    return bin(n,k-1)*(n-k+1)/k;
    
}