[Qualsiasi] Pseudo-codice per associazioni combinatorie

[Davix12]

Salve a tutti,
sapreste essermi d'aiuto per questo mio problema? Ho un vettore V di N elementi e vorrei assegnare a 3 variabili (a,b,c) tutte le combinazioni semplici di valori.
ESEMPIO: da questo vettore: N=5 [9,3,1,7,4] arrivare a tutte le 10 combinazioni semplici (ordine non importante, niente doppioni) possibili a,b,c= (V[1],V[2],V[3]; V[1],V[2],V[4]; ......)


avevo pensato ad una roba semplice del genere:

for p=1 to N {
for q=2 to N {
for r=3 to N {
a=V[p]
b=V[q]
c=V[r]
}
}
}

ma ovviamente è sbagliato perchè verrebbe fuori anche la combinazione a,b,c=(V[1],V[3],V[3]) che ripete 2 elementi


Avete qualche idea? Lo devo scrivere in Matlab, ma mi basta sapere come impostare l'algoritmo.

[Oceans11]

ma quest'algoritmo deve funzionare solo a triplette???oppure vuoi combinazioni (N,K) con K generico? (oltre che N)

[Davix12]

No, solo a triplette.

Tutte le triplette possibili senza ripetizioni e senza considerare l'ordine. a,b,c=(1,2,3) da considerare uguale a a,b,c=(2,3,1) quindi basta solo una di queste 2 combinazioni

Ad esempio se V=[1,2,3,4,5] ci sono 10 combinazioni con questi requisiti: abc=(1,2,3; 1,2,4; 1,2,5; 1,3,4; 1,3,5; 1,4,5; 2,3,4; 2,3,5; 2,4,5; 3,4,5) oppure sempre queste triplette con i singoli elementi in diverso ordine...

[Oceans11]

avevo pensato ad una roba semplice del genere:

for p=1 to N {
for q=2 to N {
for r=3 to N {
a=V[p]
b=V[q]
c=V[r]
}
}
}


ma ovviamente è sbagliato perchè verrebbe fuori anche la combinazione a,b,c=(V[1],V[3],V[3]) che ripete 2 elementi

basta che controlli che gli indici non siano uguali e sei a posto:


for(int i = 0; i < array.length; i++) {
for(int j = 0; j != i && j < array.length; j++) {
for(int k = 0; k != j && k != i && k < array.length; k++) {
System.out.println(array[i] + " " + array[j] + " " +array[k]);
}
}
}


il codice è java, per Matlab non dovrebbe essere un problema, togli la stampa a video e se non sbaglio devi far partire gli indici degli array da 1.

[Davix12]

basta che controlli che gli indici non siano uguali e sei a posto:


for(int i = 0; i < array.length; i++) {
for(int j = 0; j != i && j < array.length; j++) {
for(int k = 0; k != j && k != i && k < array.length; k++) {
System.out.println(array[i] + " " + array[j] + " " +array[k]);
}
}
}


il codice è java, per Matlab non dovrebbe essere un problema, togli la stampa a video e se non sbaglio devi far partire gli indici degli array da 1.

Ma così vengono ripetute alcune triplette solo con ordine invertito, no? Tipo mi da la tripletta con i,j,k=(1,3,5) e quella con i,j,k=(1,5,3). Invece io non vorrei triplette ripetute (anche se con ordine degli elementi divero)

[Oceans11]

no no, escono le combinazioni semplici, senza ripetizioni.


questo è l'output di una array fatto così {1, 2, 3, 4, 5}:

3 2 1
4 2 1
4 3 1
4 3 2
5 2 1
5 3 1
5 3 2
5 4 1
5 4 2
5 4 3

[Davix12]

Hai ragione, grazie mille!!!:D

Sbagliavo a riportarla in matlab :doh:

Grazie ancora!

[Oceans11]

Di niente...tra l'altro con tutti gli svarioni che sto facendo oggi, ci poteva stare che avessi sbagliato! infatti sono andato subito a controllare che mi aveva preso un colpo :D

[Vincenzo1968]

Questa è la mia versione, in C:


#include <stdio.h>

int main()
{
int k, x, y;
int a, b, c;

unsigned int DimArray;
unsigned int numeri[5];

DimArray = (sizeof(numeri) / sizeof(numeri[0]));

numeri[0] = 1;
numeri[1] = 2;
numeri[2] = 3;
numeri[3] = 4;
numeri[4] = 5;

k = 0;

printf("\n");

while ( k < DimArray - 2 )
{
a = numeri[k];

x = k + 1;
while ( x < DimArray - 1 )
{
b = numeri[x];

y = x + 1;
while ( y < DimArray )
{
c = numeri[y];

printf("%d %d %d\n", a, b, c);

y++;
}
x++;
}
k++;
}

printf("\n");

return 0;
}


Questo è il risultato su un array inizializzato con i valori 1 2 3 4 5:
http://www.guidealgoritmi.it/images/ImgForums/combinazioni.jpg