[JAVA] Combinazione di n elementi di un array

[Mister_One]

Salve ragazzi, vi riporto il mio problema:

Ho un array di n stringhe (supponiamo 4)

String string[] = new String[4];
string[0] = "a";
string[1] = "b";
string[2] = "c";
string[3] = "d";

Devo trovare tutte le possibili combinazioni senza ripetizioni (spero di aver usato il termine statistico corretto) di tali elementi dell'array.
Cioè, in questo caso dovrei avere come risultato:

ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd

Mi servirebbe un metodo Java generale (l'esempio che ho postato vale per 4 stringhe, ma il metodo dovrebbe funzionare anche per 6,7 e così via) che si occupi di restituirmi tale risultato.

Qualche consiglio?

Se avete già un metodo Java che fa tutto ciò, vi prego di postarlo

Grazie a tutti

[andbin]

Originariamente inviato da Mister_One
Devo trovare tutte le possibili combinazioni senza ripetizioni (spero di aver usato il termine statistico corretto)

Il termine è corretto, sono "combinazioni senza ripetizioni" (dette anche "combinazioni semplici").

Originariamente inviato da Mister_One
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd

Attenzione ad una cosa: sono da vedere come blocchi di combinazioni separati!! Per le combinazioni (con o senza ripetizioni) si hanno 2 parametri: un valore 'n' che indica il numero di elementi e un valore 'k' che indica la "classe". Tu vuoi generare più blocchi di combinazioni, aumentando la classe da 2 a n. Ma sono generazioni separate!!!

Con n=4 e k=2 si ha:
ab
ac
ad
bc
bd
cd

Con n=4 e k=3 si ha:
abc
abd
acd
bcd

Con n=4 e k=4 si ha:
abcd

Ma li devi trattare e generare come combinazioni del tutto separate.

Ora vediamo come farlo, che non è affatto difficile. Per farti capire meglio uso un n=6 e k=3, quindi ho lettere 'a', 'b', 'c', 'd', 'e', 'f'.

A fianco metto il corrispettivo indice nell'array (tra poco capirai perché):

abc   012
abd   013
abe   014
abf   015
acd   023
ace   024
acf   025
ade   034
adf   035
aef   045
bcd   123
bce   124
bcf   125
bde   134
bdf   135
bef   145
cde   234
cdf   235
cef   245
def   345

Che cosa noti nella progressione degli indici?? E molto semplice, se k=3 innanzitutto istanzi un array di int di 3 elementi, che contiene inizialmente i valori 0, 1, 2.

Poi l'indice più a destra si incrementa sempre fino a raggiungere il massimo (5, visto che n=6). Quando fa il "giro", la cifra appena a sinistra si incrementa di 1 e le cifre seguenti verso destra vengono messe progressivamente.

Vedi che dopo 015 c'è 023, cioè il secondo indice è passato da 1 a 2 e la cifra più a destra diventa 2+1 cioè 3.

Ogni indice ha un valore massimo che è dato da i+n-k. Quindi il primo indice può andare fino a 3 (0+6-3 = 3), il secondo indice può andare fino a 4 (1+6-3 = 4) e l'ultimo indice può andare fino a 5 (2+6-3 = 5).

Basta che realizzi una progressione degli indici come quella indicata (la devi "generalizzare", ovviamente) e poi la reale combinazione la ottieni usando gli indici nell'array dei tuoi elementi.

[rizz1]

Ciao, anche io devo risolvere lo stesso problema.
Se ho capito bene, facendo il codice col tuo esempio dovrei fare 3 cicli innestati (k=3),
dove ognuno mi scorre i tre indici?

Perchè io stavo facendo tre cicli che mi scoorono ogni indice fino a i + n-k(come giust dicevi tu), mettendo tre cicli innestati.

e come faccio visto ke poi devo far il tutto per k che va da 1 a n, ovvero dovrei fare k cicli innestati?

P.S. : Probabilmente sto ragionando male io

[Pinchia]

Salve a tutti, ho lo stesso dubbio ma non riesco ad uscirne.

Come faccio a scrivere tutte le combinazioni semplici (SENZA RIPETIZIONI) in gruppi da K elementi senza sapere quanto vale K??

Perchè io lho risolto sapendo K facendo tanti for annidati quanti sono gli elementi-K per combinazione, ma parametrizzando il calcolo come si fa?
Ricorsione? ok, ma come? non voglio sapere quante ne vengono io le voglio proprio creare!
Ma non ci riesco.

[andbin]

Originariamente inviato da Pinchia
Come faccio a scrivere tutte le combinazioni semplici (SENZA RIPETIZIONI) in gruppi da K elementi senza sapere quanto vale K??

Se intendi dire (e lo immagino) che K sia "arbitrario" cioè appunto non noto a priori, allora è chiaro che non puoi usare N cicli annidati, perché con i cicli annidati praticamente vai a "cablare" strutturalmente il numero di elementi nel gruppo, cioè appunto K.

Un modo (e non pretendo di dire che è l'unico, è quello che conosco) è di usare un array di indici e far "progredire" tali indici un po' come se fosse un sistema di numerazione ma con delle regole più particolari. Per cortesia, rileggi bene la tabellina che avevo postato nella mia prima risposta, dove ci sono le lettere e a fianco gli indici. Bene, quella è la progressione che devi realizzare, ovviamente devi generalizzarla per un qualunque K. E ti assicuro che è più facile di quanto potresti inizialmente pensare ...

E tra l'altro questa tecnica si presta bene ad essere implementata in stile "iteratore" (se conosci java.util.Iterator o simili, hai idea di cosa sto parlando).