[ FOX028 @ 14.06.2014. 15:12 ] @
POtrebna mi je pomoc ili savet. Problem se satoji u tome sto mi je potrebno da uparujem po dva elementa skupa npr.

1,2,3,4,5,6

12 34 56
12 35 46
12 36 45

itd

trebao bi da dobijem sve ovakve kombinacije s tim sto je

21 34 56 isto sto i 12 34 56

po kom bi sistemu mogao ovo da resim, tj. da se napise program
[ 3okc @ 14.06.2014. 16:27 ] @
Ovo se jako brzo iscrpljuje, sa tri gorenavedena već imaš kompletirane sve sa 12.

Pod uslovom da onih 6 članova nije podložno promeni, najlakše da završiš peške: samo nastaviš jednako i sa ostalima, poređaš ih u rastući poredak i to bi trebalo da je dovoljno (jer je 12 ≡ 21).

Ukupno je svrega 5x3 = 15 mogućih kombinacija.

12 34 56
12 35 46
12 36 45

13 24 56
13 25 46
13 26 45

14 23 56
14 25 36
14 26 35

15 23 46
15 24 36
15 26 34

16 23 45
16 24 35
16 25 34

[ FOX028 @ 14.06.2014. 16:43 ] @
pa u tome i jeste problem, nekad moze biti 6 elemenata a nekad i vise ili manje (uvek je paran broj elemenata), hehehe znam da moze peske ali to bi trebao da uradim preko VBA. Ovi elementi su ustvari cvorovi jedne transportne mreze i izmedju svakog od njih postoji odredjena udaljenost, ja bi trebao u ovom slucaju da saberem po tri grane ove mreze i da odaberem onu kombinaciju koja je najkraca.
[ 3okc @ 14.06.2014. 16:54 ] @
Onda se tu radi o matematičkom problemu poznatom kao Problem trgovačkog putnika

Verujem da ćeš lako izguglati rešenje, sva je prilika da i na ES-u postoje na drugim forumima.
[ FOX028 @ 14.06.2014. 17:15 ] @
da upravo o tome, krenuo sam da napravim program za jednu od metoda trgovackog putnika, samo sam ze zaglavio kod ovog problema.
[ djoka_l @ 15.06.2014. 12:45 ] @
Tebi, u stvari treba turnirski sistem:
http://sh.wikipedia.org/wiki/Bergerov_sistem
http://sh.wikipedia.org/wiki/Bergerove_tablice
http://sh.wikipedia.org/wiki/Aritmeti%C4%8Dki_metod_parovanja
http://sh.wikipedia.org/wiki/Grafi%C4%8Dki_metod_parovanja
http://sh.wikipedia.org/wiki/Algebarski_metod_parovanja

Naročito obrati pažnju na poslednji link, opisan je algoritam za pravljenje Bergerovih tablica.

Sa druge strane, ako ti je potreban algoritam za nalaženje najkraćeg puta u grafu, upotrebi http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Ako si zamislio da tražiš sve moguće puteve, onda je to najgori mogući algoritam...
[ FOX028 @ 15.06.2014. 16:39 ] @
hehehe ma ja sam za ovaj Dijkstra algoritam vec napravio program, ali sada sam resio da za ovaj metod napravim program. Inace radim na Visoj saobracajnoj pa me kolega profesor zamolio da mu napravim program za Dijkstru, i sada odlucio da pokusam za ovaj metod da napravim program.
[ djoka_l @ 16.06.2014. 14:24 ] @
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)



[Ovu poruku je menjao djoka_l dana 16.06.2014. u 16:02 GMT+1]