Print all possible combinations

[babel47]

Έχω τον ακόλουθο πίνακα

 

Α={ {1,2} , {3}, {4,5}, {6} }

 

1 2

3

4 5

6

 

και θέλω να εκτυπώσω όλους τους δυνατούς συνδυασμούς που μπορούν να προκύψουν από

τις στήλες του Α. Δηλαδή στην περίπτωση του συγκεκριμένου πίνακα Α θα είναι

 

1 3 4 6

2 3 4 6

1 3 5 6

2 3 5 6

 

Στην περίπτωση που ξέρω το μέγεθος του πίνακα μπορώ απλά να γράψω

 

>
for(a=1; a<4; a++){
   for(b=1; b<4; b++){
     for(c=1; c<4; c++){
for(d=1; d<4; d++){
    printf("%d %d %d %d\n",A[0][a],A[1][b],A[2][c],A[3][d]);
}
     }
   }
 }

 

Μπορεί κάποιος να υποδείξει πως μπορεί να γίνει αυτό προγραμματιστικά όταν δεν ξέρουμε το μέγεθος του πίνακα δηλαδή για ένα μεταβλητό array_length που θα δίνεται π.χ. ως όρισμα σε μία συνάρτηση και εκείνη θα πρέπει να κάνει την παραπάνω δουλειά?

 

Με λίγα λόγια αυτο που προσπαθω να φτιακσω ειναι μια συναρτηση η οποια θα παιρνει σαν ορισμα το μεταβλητό μηκος του πινακα και θα εκτυπωνει ολους τους δυνατους συνδυασμους που αναφερονται παραπάνω. Ο πινακας θα είναι global.

[parsifal]

Ο πίνακάς σου είναι 2D. Ποια διάστασή του ονομάζεις «μήκος»; Τις γραμμές ή τις στήλες;

 

Η συνάρτηση θα πρέπει να υποστηρίζει μεταβλητό μέγεθος μόνο στη μία διάσταση ή και στις δύο... ;

[babel47]

Συγκεκριμένα ο πίνακας θα είναι ένας σταθερός αλλά αρκετά μεγάλης διάστασης global πίνακας 2D όπως λες και εσυ. Θα δίνω σαν ορισμα τον αριθμό της γραμμής αρχής και τον αριθμό της γραμμής τέλους, ο οποίες θα ορίζουν ένα σύνολο γραμμών πάνω στο οποίο θα εκτυπώνονται όλοι οι δυνατοί συνδυασμοί όπως αναφέρεται στο προηγούμενο ποστ μου.

 

Δηλαδή εαν ο πινακας ειναι ο

 

Α =

 

1 2

4

5

7

3 4

5

6 7 8

9

3

4

 

και καλέσω την function(4,6) θα πρεπει να εκτυπωθεί σαν αποτέλεσμα

 

3 5 6

4 5 6

3 5 7

4 5 7

3 5 8

4 5 8

 

δηλαδη κατι σαν ολους τους συνδυασμούς στηλων των γραμμων

 

3 4

5

6 7 8

[bxenos]

Να μια ιδέα για τη λύση:

 

Υπάρχει ορισμένος ένας πίνακας xList[N] με members xList

 

Καθε xList είναι μια απλά συνδεδεμένη λίστα με Nodes. Εχει έναν δείκτη head σε Node.

 

Καθε Node έχει έναν ακεραιο και ένα pointer next (στον επόμενο Node).

 

C++ code:

>
void run(xList *A,size_t start,size_t end,size_t iter=0,xList::ptr *curr=NULL){
//αναδρομική συνάρτηση που υπολογίζει ολους τους συνδιασμους
//στον πίνακα Α μεταξύ του [start,end). 
//Το iter είναι εσωτερικός μετρητης του recursion και ξεκινά απο
//0 εως end-start. 
//Σημαινει οτι ο πίνακας απο [start,start+iter) είναι έτοιμος
//(οπότε στην τρέχουσα κληση πρεπει να φροντίσουμε 
//για τις θέσεις [start+iter,end)
if(iter == 0){
	//Είναι η πρώτη μας κληση στο recursion και βρισκόμαστε στο επίπεδο 0
	//(ψαχνουμε δηλαδη τιμή για το A[start].
	//Δημιουργησε πίνακα δεικτών σε Node (τρέχουσα instance της αναδρομής μας)
	assert(curr == NULL);
	if(end>start){
		//πίνακας για την τρέχουσα instance του πίνακα A.
		curr = new xList::ptr[end - start];
	}
}
if(curr){
	if(start+iter == end){
		for(size_t i=0;i<iter;i++){
			assert(curr[iter]!=NULL);
			printf("%d ",curr[i]->a);
		}
		putchar('\n');
		return;
	}
	for(curr[iter] = A[start+iter].head; curr[iter]!=NULL; curr[iter] = curr[iter]->next)
		run(A,start,end,iter+1,curr);
	
}
if(iter == 0){
	//τέλος όλης της αναδρομης.
	//Απελευθέρωσε πίνακα δεικτών
	delete []curr;
}
}

int main(void){
...δεσμευσε πίνακα Α...
...δωσε αρχικές τιμές...
run(A,0,4);	//βρες συνδιασμούς στις θεσεις [0,4)
...απελευθέρωσε πίνακα...
return 0;
}

 

να ο πίνακας μας με τα δεδομένα και τα αποτελεσματα:

 

 

πίνακας

1 0 4

1

1 2 6

1

1 4 8

1

1 6 0

1

1 8 2

1

1 0 4

1

1 2 6

1

1 4 8

1

1 6 0

1

1 8 2

1

1 0 4

1

1 2 6

1

1 4 8

1

1 6 0

1

1 8 2

1

 

να και τα αποτελεσματα της κλησης run(A,0,4)

4 1 6 1

4 1 2 1

4 1 1 1

0 1 6 1

0 1 2 1

0 1 1 1

1 1 6 1

1 1 2 1

1 1 1 1

 

 

Δεν έδωσα όλα τα στοιχεία του κώδικα για να μπορέσεις να κάνεις τα υπόλοιπα μόνος σου.

[bxenos]

τα κατάφερες τελικά;