COmbinare elementi Array

di
Arsene
il
7 risposte
Arsene
Arsene
Pochi posts
Iscritto da
dic, 2011
Messaggi:
8

COmbinare elementi Array

Salve a tutti,
Ho il seguente problema in C++ da sottoporvi: Ho un array[m][n] con m ed n dimensioni non note apriori ma definite durante l'esecuzione del programma. Ogni elemento dell'array è un numero intero diverso da 0 e ho qualcosa del genere:
Array 1 2 3 4 ..... (n)
________________________
1 | 1 5 8 . .... .
2 | 2 6 6 .
3 | 3 -2 9 .
. | 4 -2 -2 .
. | . . . .
(m) | . . . ... .

dove -2 mi indica che quella posizione dell'array non è stata riempita.
Vorrei ottenere in qualche modo tutte le possibili combinazioni degli elementi delle colonne,
ovvero supponendo di considerare la sottomatrice 3x3 rappresentata vorrei:
(1,5,8) (1,5,6) (1,5,9) (2,5,8) (2,5,6) (2,5,9) ... (4,3,9)
(in uno stesso sottoinsieme non devono essere present elemnti della stessa colonna, a meno che non compaiano anche nelle colonne successive...)
Non so veramente come fare, mi verrebbe da implementare tanti cicli for quante colonne ma non conoscendoli apriori non posso farlo... vi sarei grato se aveste qualche suggerimento. A.

7 Risposte

  • A
    AlessandroS
    Utente Attivo
    Iscritto da
    nov, 2011
    Messaggi:
    128

    Re: COmbinare elementi Array

    Ciao ,

    Scusami ma non ho capito bene queste combinazioni ... esempio se io ho una matrice 3x3 in questo modo :
    3 4 5
    3 -2 7
    2 9 8
    Quali sono tutte le possibili combinazioni?
  • V
    Vins3Xtreme
    Utente Attivo
    Iscritto da
    dic, 2011
    Messaggi:
    144

    Re: COmbinare elementi Array

    Beh, se sai come allocare dati in memoria dinamicamente, ovvero utilizzando i puntatori, potresti dichiararti un tipo Matrice che sia un 'int**' ad esempio, per poi allocare dinamicamente in base ai dati forniti da tastiera: 
    
//esempio
typedef int** Matrice;
    Oppure, se ancora non hai studiato i puntatori, potresti definirti il tipo Matrice con dimensioni massime fisse, ad esempio: 
    
#define RowMAX 100 // <---100 è un esempio, puoi metterci il valore che vuoi
#define ColMAX 100  // <--- idem

typedef int Matrice[RowMAX][ColMAX]
    per poi inserire da tastiera le dimensioni effettive da utilizzare con la Matrice (attenzione però che i valori immessi non superino RowMAX e ColMAX).
    Per quanto riguarda invece l'ottenimento di tutte le possibili combinazioni,l'idea di utilizzare dei for è una possibilità, anche se per ogni colonna sarebbe un pò ostico (immagina 20 colonne!). un idea sarebbe quella di utilizzare una funzione ricorsiva. Comincia a scrivere del codice, poi postalo così possiamo risolvere insieme il problema.
  • Arsene
    Arsene
    Pochi posts
    Iscritto da
    dic, 2011
    Messaggi:
    8

    Re: COmbinare elementi Array

    AlessandroS ha scritto:

    Ciao ,

    Scusami ma non ho capito bene queste combinazioni ... esempio se io ho una matrice 3x3 in questo modo :
    3 4 5
    3 -2 7
    2 9 8
    Quali sono tutte le possibili combinazioni?

    Ciao AlessandroS,

    le combinazioni in questo caso sarebbero (3,4,5) (3,4,7) (3,4,8) (3,9,5) (3,9,7) (3,9,8)
    (3,4,5) (3,4,7) (3,4,8) (3,9,5) (3,9,7) (3,9,8) (2,4,5) (2,4,7) (2,4,8) (2,9,5) (2,9,7) (2,9,8)
    Anche se ho dimenticato di dire che lo stesso numero (il 3 nella tua sottomatrice) non può comparire nella stessa colonna, mentre può essere presente sulla stessa riga...(per come ho costruito la matrice)
  • Arsene
    Arsene
    Pochi posts
    Iscritto da
    dic, 2011
    Messaggi:
    8

    Re: COmbinare elementi Array

    Ciao Vins3Xtreme,

    uno dei miei problemi è che, essendo questo un sottoproblema di un algoritmo che sto scrivendo, "sfioro" continuamente il problema di overflow quindi non so se fissare le dimensioni massime può generarmi problemi ulteriori...sto studiando diverse soluzioni, forse potrei creare una struttura ad albero ma anche qui ho difficolta' nel farlo...
  • V
    Vins3Xtreme
    Utente Attivo
    Iscritto da
    dic, 2011
    Messaggi:
    144

    Re: COmbinare elementi Array

    Se nell'algoritmo che stai scrivendo hai la possibiltà di controllare l'input da tastiera, allora la definizione delle dimensioni massime di riga e colonna non dovrebbero darti problemi. L'utilità dell'allocazione dinamica sarebbe quella di occupare solo lo spazio necessario. per le combinazini, ripeto, sarebbe una soluzione l'utilizzo dei cicli for con una funzione ricorsiva. Immagino che il numero di combinazioni 'totali' sia la potenza M di N , con N numero di righe e M numero di colonne. Ad esempio una matrice 3righe x 4 colonne, il numero totale di combinazioni sarà (3^4)= 81 combinazioni totali.
  • A
    AlessandroS
    Utente Attivo
    Iscritto da
    nov, 2011
    Messaggi:
    128

    Re: COmbinare elementi Array

    Arsene per una matrice 3x3 per tutte le possibili combinazioni tranne quelle dove si trova -2 ho pensato a questa cosa qui:
    
void stampa ( matrice mat , int prima , int seconda , int terza ) {  
	if ( (mat[prima][0] != -2) && (mat[seconda][1] != -2) && (mat[terza][2] != -2) )
	   cout << "(" << mat[prima][0] << "," << mat[seconda][1] << "," << mat[terza][2]<< ")"<<endl;
}

void combinazioni ( matrice mat, int n , int prima , int  seconda , int  terza ) {
 if (prima != n )
 {
	if ( terza == n-1 )
	{
		stampa(mat,prima,seconda,terza);
		if ( seconda == n-1)
			combinazioni(mat,n,prima+1,0,0);
		else
			combinazioni(mat,n,prima,seconda+1,0);
	}
	else
	{
		stampa(mat,prima,seconda,terza);
		combinazioni(mat,n,prima,seconda,terza+1);
	}
 }
}
    Dove prima seconda e terza sta per le righe di una matrice, matrice sarà un tipo che lo puoi benissimo definire con un typedef . CI potrebbero essere dei miglioramenti per quanto riguarda l' algoritmo ( esempio si potrebbe mettere un if nel quale se nella seconda colonna c'è un -2 allora si passa automaticamente a quella dopo e si saltano molte ricorsioni ) .


    Vedi se da questo puoi fare qualcosa per una matrice nxm che cmq non ho capito bene le combinazioni di una matrice nxm come dovrebbero essere.
  • Arsene
    Arsene
    Pochi posts
    Iscritto da
    dic, 2011
    Messaggi:
    8

    Re: COmbinare elementi Array

    Grazie ragazzi per l'aiuto, sto provvedento a implementare una funzione ricorsiva...
Devi accedere o registrarti per scrivere nel forum
7 risposte