Evo ti algoritam, ako još nisi smislio:
1. Uzmi da je tekuća grupa ona koja je pretposlednja.
1. Zapamti desni element tekuće grupe.
2. uporedi ga sa svim ostalim elementima ostalih (desnih) grupa i nadji minimalan element koji je veći od tog zapamćenog
3. Ako je takav element pronađen, zameni ga sa elementom na poslednjem mestu tekuće grupe, a elemente ostalih grupa desno od tekuće sortiraj i ispiši kombinaciju.
4. Ako nije pronađen, pomeri se za jednu grupu u levo i ponovi postupak dok ne potrošiš sve grupe.
Bilo mi je zgodnije da napišm kod u C-u
Code (c):
/*Hederi potrebni zbog printf i qsort */
#include <stdio.h>
#include <stdlib.h>
/* compare funkcija za qsort */
int compare
(const void * a
, const void * b
)
{
return ( *(int*)a
- *(int*)b
);
}
/* Zamena dva elementa niza */
void Swap
( int* l
, int* r
) {
int t
= *l
;
*l
= *r
;
*r
= t
;
}
/* Funkcija FindMin
** pronalazi u nizu "arr" indeks najmanjeg elemnta
** izmedju indeksa "start" i "end" koji je veci od "elem".
** Vraca indeks ili 0 ako takav element nije pronadjen.
*/
int FindMin
( int arr
[], int start
, int end
, int elem
) {
int i
,min
;
int p
=0;
for( i
=start
; i
<end
; i
++){
if((arr
[i
] > elem
)) {
if(p
==0) {
p
=i
;
min
=arr
[i
];
}
else {
if(arr
[i
]<min
){
min
=arr
[i
];
p
=i
;
}
}
}
}
return p
;
}
/* Funkcija Next
** pronalazi sledecu ispravnu kombinaciju parova nad nizom "Curr"
** od "n" elemenata.
** U slucaju da postoji sledeca kombinacija vraca 1, inace 0.
*/
int Next
( int* Curr
, int n
) {
int i
;
int group
=n
/2-1;
int m
;
for(i
=2*group
-1; i
>0; i
-=2) {
if(Curr
[i
]<n
) {
if( m
=FindMin
(Curr
, i
+1, n
, Curr
[i
]) ) {
Swap
( &Curr
[i
], &Curr
[m
]);
qsort(&Curr
[i
+1], n
-i
-1, sizeof(int), compare
);
return 1;}
}
}
return 0;
}
int main
() {
int niz
[] = {1,2,3,4,5,6,7,8};
int n
=8;
int i
,k
=1;
do {
printf("%3.1d: ",k
++);
for(i
=0; i
<n
/2; i
++) printf("(%d,%d) ", niz
[2*i
], niz
[2*i
+1]);
printf("\n");
} while( Next
(niz
, n
));
}
Rezultat:
Code:
$ make combinations
cc combinations.c -o combinations
$ ./combinations.exe
1: (1,2) (3,4) (5,6) (7,8)
2: (1,2) (3,4) (5,7) (6,8)
3: (1,2) (3,4) (5,8) (6,7)
4: (1,2) (3,5) (4,6) (7,8)
5: (1,2) (3,5) (4,7) (6,8)
6: (1,2) (3,5) (4,8) (6,7)
7: (1,2) (3,6) (4,5) (7,8)
8: (1,2) (3,6) (4,7) (5,8)
9: (1,2) (3,6) (4,8) (5,7)
10: (1,2) (3,7) (4,5) (6,8)
11: (1,2) (3,7) (4,6) (5,8)
12: (1,2) (3,7) (4,8) (5,6)
13: (1,2) (3,8) (4,5) (6,7)
14: (1,2) (3,8) (4,6) (5,7)
15: (1,2) (3,8) (4,7) (5,6)
16: (1,3) (2,4) (5,6) (7,8)
17: (1,3) (2,4) (5,7) (6,8)
18: (1,3) (2,4) (5,8) (6,7)
19: (1,3) (2,5) (4,6) (7,8)
20: (1,3) (2,5) (4,7) (6,8)
21: (1,3) (2,5) (4,8) (6,7)
22: (1,3) (2,6) (4,5) (7,8)
23: (1,3) (2,6) (4,7) (5,8)
24: (1,3) (2,6) (4,8) (5,7)
25: (1,3) (2,7) (4,5) (6,8)
26: (1,3) (2,7) (4,6) (5,8)
27: (1,3) (2,7) (4,8) (5,6)
28: (1,3) (2,8) (4,5) (6,7)
29: (1,3) (2,8) (4,6) (5,7)
30: (1,3) (2,8) (4,7) (5,6)
31: (1,4) (2,3) (5,6) (7,8)
32: (1,4) (2,3) (5,7) (6,8)
33: (1,4) (2,3) (5,8) (6,7)
34: (1,4) (2,5) (3,6) (7,8)
35: (1,4) (2,5) (3,7) (6,8)
36: (1,4) (2,5) (3,8) (6,7)
37: (1,4) (2,6) (3,5) (7,8)
38: (1,4) (2,6) (3,7) (5,8)
39: (1,4) (2,6) (3,8) (5,7)
40: (1,4) (2,7) (3,5) (6,8)
41: (1,4) (2,7) (3,6) (5,8)
42: (1,4) (2,7) (3,8) (5,6)
43: (1,4) (2,8) (3,5) (6,7)
44: (1,4) (2,8) (3,6) (5,7)
45: (1,4) (2,8) (3,7) (5,6)
46: (1,5) (2,3) (4,6) (7,8)
47: (1,5) (2,3) (4,7) (6,8)
48: (1,5) (2,3) (4,8) (6,7)
49: (1,5) (2,4) (3,6) (7,8)
50: (1,5) (2,4) (3,7) (6,8)
51: (1,5) (2,4) (3,8) (6,7)
52: (1,5) (2,6) (3,4) (7,8)
53: (1,5) (2,6) (3,7) (4,8)
54: (1,5) (2,6) (3,8) (4,7)
55: (1,5) (2,7) (3,4) (6,8)
56: (1,5) (2,7) (3,6) (4,8)
57: (1,5) (2,7) (3,8) (4,6)
58: (1,5) (2,8) (3,4) (6,7)
59: (1,5) (2,8) (3,6) (4,7)
60: (1,5) (2,8) (3,7) (4,6)
61: (1,6) (2,3) (4,5) (7,8)
62: (1,6) (2,3) (4,7) (5,8)
63: (1,6) (2,3) (4,8) (5,7)
64: (1,6) (2,4) (3,5) (7,8)
65: (1,6) (2,4) (3,7) (5,8)
66: (1,6) (2,4) (3,8) (5,7)
67: (1,6) (2,5) (3,4) (7,8)
68: (1,6) (2,5) (3,7) (4,8)
69: (1,6) (2,5) (3,8) (4,7)
70: (1,6) (2,7) (3,4) (5,8)
71: (1,6) (2,7) (3,5) (4,8)
72: (1,6) (2,7) (3,8) (4,5)
73: (1,6) (2,8) (3,4) (5,7)
74: (1,6) (2,8) (3,5) (4,7)
75: (1,6) (2,8) (3,7) (4,5)
76: (1,7) (2,3) (4,5) (6,8)
77: (1,7) (2,3) (4,6) (5,8)
78: (1,7) (2,3) (4,8) (5,6)
79: (1,7) (2,4) (3,5) (6,8)
80: (1,7) (2,4) (3,6) (5,8)
81: (1,7) (2,4) (3,8) (5,6)
82: (1,7) (2,5) (3,4) (6,8)
83: (1,7) (2,5) (3,6) (4,8)
84: (1,7) (2,5) (3,8) (4,6)
85: (1,7) (2,6) (3,4) (5,8)
86: (1,7) (2,6) (3,5) (4,8)
87: (1,7) (2,6) (3,8) (4,5)
88: (1,7) (2,8) (3,4) (5,6)
89: (1,7) (2,8) (3,5) (4,6)
90: (1,7) (2,8) (3,6) (4,5)
91: (1,8) (2,3) (4,5) (6,7)
92: (1,8) (2,3) (4,6) (5,7)
93: (1,8) (2,3) (4,7) (5,6)
94: (1,8) (2,4) (3,5) (6,7)
95: (1,8) (2,4) (3,6) (5,7)
96: (1,8) (2,4) (3,7) (5,6)
97: (1,8) (2,5) (3,4) (6,7)
98: (1,8) (2,5) (3,6) (4,7)
99: (1,8) (2,5) (3,7) (4,6)
100: (1,8) (2,6) (3,4) (5,7)
101: (1,8) (2,6) (3,5) (4,7)
102: (1,8) (2,6) (3,7) (4,5)
103: (1,8) (2,7) (3,4) (5,6)
104: (1,8) (2,7) (3,5) (4,6)
105: (1,8) (2,7) (3,6) (4,5)