[C] Generazione Combinazioni ???

[kNemo]

Per calcolo dovrei fare un generatore di Combinazioni...
Solo che non so' quasi da dove iniziare...

Dovrei generare tutte le combinazioni di n lettere...
Io Ho provato a farlo con due e sembra funzionare...
Solo che questo metodo non mi sembra il migliore anche perche'
non saprei come fare n cicli...

Qualcuno sa' darmi una mano... Grazie.

#include <stdio.h>

#define START		 97
#define END	        122

int main() {
	unsigned short int i, j;
	unsigned short int start = 0;
	
	for (j=START; j <= END; j++) {
		start = 0;
		for (i=START; i <= END; i++) {
			if (i == START && !start) {
				i = 0;
				start = 1;
			}
			printf("%c%c\n", j, i);
			if (i == 0) i = START;
		}		
	}
	return (0);
}

[Anªkin]

chiarisci. vuoi calcolare tipo tutte le combinazioni (o permutazioni?) sull'insieme di tutte le lettere? Cioé avendo 25 elementi(lettere) vuoi avere restituite tutte le parole di lunghezza k che si ottengono alternando tutte le lettere?

[Iena87]

Credo si riferisca alle permutazioni, dovendo generare delle combinazioni dove date n lettere, queste devono essere cambiate d'ordine...almeno credo


La formula per il calcolo delle permutazioni è la seguente:

Pn= n! / n1!*n2!...

n! è facile ricavarlo, il problema sono le n! di sotto, che indicano le lettere che si ripetono in una parola...come si fa?

[Anªkin]

per quanto riguarda le permutazioni ho trovato questa:
Permutazioni:

Supponiamo di avere 3 oggetti {a,b,c}; 
questi potranno essere ordinati in 6 modi diversi:

1 = {a,b,c} 2 = {b,c,a} 3 = {c,a,b} 
4 = {a,c,b} 5 = {b,a,c} 6 = {c,b,a} 

Quindi le permutazioni di 3 oggetti sono 6.

P(N) = N!

Combinazioni:

Supponiamo di avere 3 oggetti {a,b,c} e di prenderli a gruppi di 2; 
i modi con cui possiamo farlo sono: 

1 = {a,b} 2 = {a,c} 3 = {b,c} 

Quindi le combinazioni di 3 oggetti di classe 2 (= presi a 2 per volta) sono 3.

C(N,k) = N!/(N-k)!

Ma mi sono impantanato nel generare le Combinazioni vere e proprie, mo provo con le permutazioni

edit non permutazioni, volevo dire disposizioni N!/(N-k)!

[andrea_NET-_DSL]

Originariamente inviato da Anªkin
C(N,k) = N!/(N-k)!

No,le COMBINAZIONI si calcolano con la formula:

n!/(n-k)!*k!

quelle sono le DISPOSIZIONI ...anche se c'è una formula "migliore",nel senso + adatta per risolvere questo problema a livello informatico e con cui si puù sfruttare la ricorsione.

Sto scrivendo l'algortimo in c...tra poco te lo posto



ps parliamo sempre di combinazioni e disposizioni SEMPLICI...cioè senza ripetizione

[andrea_NET-_DSL]

Applichiamo le DISPOSIZIONI in modo tale da ottenere su n lettere(25 quelle dell'alfabeto) delle parole di lunghezza k.

Essendo DISPOSIZIONI una parola differisce dall'altra non solo per l'ordine,ma anche per gli elementi che le compongono.(come giusto DEVE essere per quanto riguarda le parole...infatti "aba" e "baa" non sono uguali o no? :gren: )
La formula è:
D(n,k) = n * (n-1) * (n-2)* ... * (n-k+1)

#include <stdio.h>
int disposizioni_semplici(int ,int ,int );

const int n=25; //lettere alfabeto italiano

int main(){

int k=0;//classe
printf("\nInserisci la lunghezza delle parole da considerare\n");
scanf("%d",&k);

if (n>k)  printf("\nCon %d lettere puoi avere %d parole di lunghezza %d",n,disposizioni_semplici(k,n,n),k);
  else printf("\nImpossibile eseguire l'operazione\n");

return 0;
}

/* calcolo in modo ricorsivo*/
int disposizioni_semplici(int k,int n,int m){
if ( n== m-k ) return 1;
else 
 return ( n*disposizioni_semplici(k,n-1,m) );
}

provalo cmq

ciao

[kNemo]

a me' non interessa il numero di combinazioni possibili...
mi interessano le combinazioni vere e proprie...

a
aa
ab
ac
..

[LeleFT]

Originariamente inviato da andrea_NET-_DSL
Applichiamo le DISPOSIZIONI in modo tale da ottenere su n lettere(25 quelle dell'alfabeto) delle parole di lunghezza k.

PS: Le lettere dell'alfabeto sono 26. Quelle dell'alfabeto italiano sono 21.


Ciao.

[anx721]

Per impostare un algoritmo (ricorsivo) usa la seguente osservazione: una combinazione di lunghezza n la ottieni inserendo un qlsiasi carattere in una qualsiasi posizione in una combinazione di lunghezza n - 1, ovvero tutte le combinazioni di lunghezza n le ottieni concatenando uno alla volta tutti i caratteri in tutte le n posizionni di tutte le combinazioni di lunghezza n - 1.

[kNemo]

L'ho riletta 32 volte e ho capito ancora poco