[algoritmi] Elenco combinazioni

[daneel]

Riapro una discussione che è andata cancellata insieme agli altri thread delle 24 ore precedenti la chiusura del forum.
Esistono uno o più algoritmi sufficientemente efficienti da essere in grado di elencare tutte le possibili permutazioni, disposizioni o combinazioni di n presi ad m ad m con o senza ripetizioni (dove n ed m sono numeri non troppo grandi)?
Ho scritto una funzione in Python che calcoli le disposizioni con ripetizione per n simboli dati, basata su una funzione random che viene eseguita fino al raggiungimento del totale delle disposizioni n^m. L'esecuzione è molto veloce, ma l'algoritmo non mi sembra dei migliori.

n=("a","b","c")
m=4
d=[]

from math import pow
t=pow(len(n),m)

from random import randint
while len(d)<t:
	e=""
	for i in range(m):
		e+=str(randint(0,len(n)-1))
	for i in range(len(n)):
		e=e.replace(str(i),n&#091;i])
	if not d.__contains__(e):
		d.append(e)

d.sort()
d=&#091;"%d - %s" % (d.index(e)+1,e) for e in d]
for i in d: print i

C'era stato chi mi aveva chiesto di trascriverle, quindi riporto le formule per calcolare il numero di disposizioni, permutazioni e combinazioni (per comodità evito la notazione con i coefficienti binomiali).
Per calcolare il numero di disposizioni: D=n!/(n-m)!
Permutazioni: P=n!
Combinazioni: C=n!/(m!(n-m)!)
Disposizioni con ripetizione: D'=n^m (n elevato a m)
Permutazioni con ripetizione: P'=n!/m!
Combinazioni con ripetizione: (n-1+m)!/((n-1)!m!)

[daneel]

up

[eagle_fly]

Non so se ti può essere di aiuto me per risolvere questi problemi io uso la ricorsione (i programmi sono scritti in c!)!
Non so come funziona il Python, ma penso che in c potendo sfruttare la ricorsione questi problemi sono ben risolti con questo linguaggio!!

CIAO

[daneel]

Originariamente inviato da eagle_fly
Non so se ti può essere di aiuto me per risolvere questi problemi io uso la ricorsione (i programmi sono scritti in c!)!
Non so come funziona il Python, ma penso che in c potendo sfruttare la ricorsione questi problemi sono ben risolti con questo linguaggio!!
CIAO

Con Python è possibile scrivere funzioni ricorsive (anche se ora ho scelto Python solo per comodità, poi potrei portare tutto in C++). Potresti farmi qualche esempio? Grazie.

[eagle_fly]

Ecco un esempio per il calcolo delle dispoizioni semplici in C:

#include <stdio.h>

// Calcolo delle disp semp. di n oggetti di classe k

int dispo(int, int, int);

void main()
{
    int n, k;

    printf("\nDISP. SEMPLICI DI N OGGETTI PRESI K PER VOLTA");
    printf("\nInserire n: ");
    scanf("%d", &n);
    printf("\nInserire k: ");
    scanf("%d", &k);

    printf("\nLe disp. semplici di %d di classe %d è: %d", n, k,  dispo(k, n, n));
}

int dispo(int k, int n, int m)
{
    if(n==m-k)
        return(1);
    else
        return(n*dispo(k, n-1, m));
}

Per le combinazioni semplici si usa la stessa struttura dividendo il risultato delle dispo per il fattoriale di k, e quindi si utilizzeranno tre funzioni ricorsive, una per le combi, l'altra per le dispo, e l'ultima per il calcolo del fattoriale in questo modo:

int comb(int k, int n)
{
     return(dispo(k, n, n)/fat(k));
}

int dispo(int k, int n, int m)
{
     if(n==m-k)
          return(1);
     else
          return(n*dispo(k, n-1, m));
}

int fat(int n)
{
     if(n==0)
          return 1;
     else
        return(n*fatt(n-1));
}

Spero ti possano andare bene!!
CIAO

[daneel]

Ti ringrazio per l'aiuto, eagle_fly, ma ero curioso di sapere se è possibile elencare in qualche modo tutte le possibili disposizioni o combinazioni, e non solo conoscerne il numero.