Algoritmo per la ricerca delle combinazioni

Qualche anno fa mi sono trovato nella necessità di creare un algoritmo per ricavare le possibili combinazioni di n elementi su k posizioni: questo mi serviva per sviluppare un sistema per il totogol su Excel (quindi n numeri di mia scelta su 8 posizioni).

Qui sotto trovate l'algoritmo implementato sia in linguaggio C che in Python.

Avevo affrontato il problema sviluppando la seguente funzione ricorsiva in C:

void combina(char* data, int n, int k, char* out_str, int out_pos)
{
  int i;
	
  for (i=0; i<=(n-k); i++)
  {
    out_str[out_pos]=data[i];
    if(k > 1)
    {
      combina(&data[i+1], (n-1-i), (k-1), out_str, (out_pos+1));
    }
    else
    {
      out_str[out_pos+1]=0;
      printf(out_str);
      putchar('\\n');
    }
  }
}

Tale funzione si limita a stampare a video il risultato delle possibili combinazioni di un array di n caratteri di classe k.
Segue un esempio di chiamata:

int main(int argc, char *argv[])
{
  char car[] = {'A', 'B', 'C', 'D', 'E'};
  char comodo[6];
	
  combina(car, 5, 3, comodo, 0);
  printf ("\nPremi un tasto\n");
  getch();
  return 0;
}

Il risultato a video è il seguente:

ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE

Negli ultimi mesi ho iniziato ad utilizzare Python e ho provato quindi a riscrivere la funzione in questo linguaggio.

def combinaric( lst, set, curr, n, k ):
    #print( "combinaric: n=" + str(n) + " k=" + str(k) + " curr=" + curr)
        
    for i in range(0,len(set)):
        loccurr = curr + set[i]
        if k==1:
            lst.append(loccurr)
        else:
            combinaric( lst, set[i+1:], loccurr, n-1, k-1)

def combina( set, k ):
    lst = [];
    n = len(set)
    combinaric( lst, set, "", n, k )
    return lst
    
if __name__ == "__main__":
    lst = combina( "ABCDE", 3 )
    for i in range(0,len(lst)):
        print("->"+lst[i])

Nell'implementazione in linguaggio Python ho voluto introdurre:

1) una funzione intermedia (combina) che si occupa di fare la prima chiamata alla funzione ricorsiva, gestendo al suo interno quindi la creazione di una lista di risultati vuota e l'inizializzazione della stringa curr contenente il risultato corrente, per semplificare la vita al chiamante;

2) separare l'esecuzione dell'algoritmo dalla visualizzazione dei risultati, semplicemente caricando in una lista tutti i risultati trovati.