compte la complexité et implementation de ClasseUnionCompress
authorDralagen <dralagen@dralagen.fr>
Tue, 3 Dec 2013 17:26:19 +0000 (18:26 +0100)
committerDralagen <dralagen@dralagen.fr>
Tue, 3 Dec 2013 17:26:19 +0000 (18:26 +0100)
Makefile
src/ChercherMin.java
src/ClasseUnion.java
src/ClasseUnionCompress.java [new file with mode: 0644]
src/Paire.java
src/Permutation.java
src/Prog.java

index 2b9df47..c555462 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
 CC=javac
-CFLAGS= -g -d bin/ -s src/
+CFLAGS=-d bin/ -s src/
 EXEC=intCommun
 SRC= $(wildcard src/*.java)
 OBJ=$(CLASSES:.java=.class)
@@ -7,8 +7,10 @@ OBJ=$(CLASSES:.java=.class)
 all: $(EXEC)
 
 intCommun: $(OBJ)
+       mkdir -p bin
        $(CC) $(CFLAGS) $(SRC)
 
+
 .PHONY: clean mrproper
 
 clean:
index f814a07..c677fbf 100644 (file)
 import java.util.ArrayList;
 
 public class ChercherMin {
-       /*
-        * P = (6 2 3 5 4 7 1 8)
-        * R = {(1,2),(3,7),1,4)}
-        * 
-        */
-       public static void CURang(Permutation P, ArrayList<Paire> R) {
+       public static int comp=0;
+       public static int[] CURang(Permutation P, ArrayList<Paire> R) {
+               comp=0;
+               int[] mins = new int[R.size()];
                /*
                 * Coll : ({},id)
                 * 
                 */
                ClasseUnion C = new ClasseUnion(P.getN()+2);
+               // calcule dans la classe
+               comp++; // calcule param
                
+               comp+=2; // init  + test
+               for (int h = 0; h <= P.getN(); h++) {
+                       comp+= 2; // test+ incrementation
+                       
+                       int ph = P.getElts(h);
+                       comp++;
+                       
+                       comp++; // test
+                       for(Coll c : C.getColl()){
+                               comp++; // init
+                               comp++; // test
+                               if (!c.empty()) {
+                                       comp++; // test
+                                       if (c.getId() >= ph) {
+                                               C.union(ph,c.getId()); // calcul dans union
+                                       }
+                               }
+                       }
+                       
+                       //calcule dans union
+                       C.add(ph,h);
+                       
+                       comp++; // test
+                       for(Paire pr : R) {
+                               comp++; // affectation
+                               comp++; // test
+                               if (h == pr.getB()) {
+                                       mins[Math.min(P.getElts(pr.getA()),P.getElts(pr.getB()))-1] = C.classeVal(pr.getA());
+                                       //System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
+                               }
+                       }
+                       //System.out.println(C);
+               }
+               System.out.println(comp);
+               return mins;
+       }
+       
+       public static int[] CURangCompress(Permutation P, ArrayList<Paire> R) {
+               comp = 0;
+               int[] mins = new int[R.size()];
+               /*
+                * Coll : ({},id)
+                * 
+                */
+               ClasseUnionCompress C = new ClasseUnionCompress(P.getN()+2);
+               // calcule dans la classe
+               comp++; // calcule param
                
+               comp+=2; // init  + test
                for (int h = 0; h <= P.getN(); h++) {
+                       comp+= 2; // test+ incrementation
+                       
                        int ph = P.getElts(h);
+                       comp++;
+                       
+                       comp++; // test
                        for(Coll c : C.getColl()){
+                               comp++; // init
+                               comp++; // test
                                if (!c.empty()) {
+                                       comp++; // test
                                        if (c.getId() >= ph) {
-                                               C.union(ph,c.getId());
+                                               C.union(ph,c.getId()); // calcul dans union
                                        }
                                }
                        }
                        
-                       //C.creer(ph);
+                       //calcule dans union
                        C.add(ph,h);
                        
+                       comp++; // test
                        for(Paire pr : R) {
+                               comp++; // affectation
+                               comp++; // test
                                if (h == pr.getB()) {
-                                       
-                                       System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
+                                       mins[Math.min(P.getElts(pr.getA()),P.getElts(pr.getB()))-1] = C.classeVal(pr.getA());
+                                       //System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
                                }
                        }
-                       System.out.println(C);
+                       //System.out.println(C);
                }
+               System.out.println(comp);
+               
+               return mins;
        }
 }
index 3c30b45..4819cbb 100644 (file)
@@ -5,35 +5,50 @@ public class ClasseUnion {
        
        public ClasseUnion(int t){
                p_ = new int[t];
+               ChercherMin.comp++; //init
                ens_ = new Coll[t];
+               ChercherMin.comp++; //init
+               
+               ChercherMin.comp+=2; // init + test
                for (int i = 0; i < t; i++) {
+                       ChercherMin.comp+=2; // test + incrementation
+                       
                        p_[i] = -1;
+                       ChercherMin.comp++;
                        ens_[i] = new Coll(i);
+                       ChercherMin.comp++;
                }
                
        }
        
        public int classe(int i) {
                while (p_[i] != -1 ) {
+                       ChercherMin.comp++; //test
                        i = p_[i];
+                       ChercherMin.comp++; //affectation
                }
+               ChercherMin.comp++; //test
                return i;
        }
        
        public void union(int a, int b) {
+               ChercherMin.comp++; // test
                if (classe(a) != classe(b)) {
                        p_[b] = a;
 
                        ens_[a].add(ens_[b]);
                        ens_[b].resetEns();
+                       ChercherMin.comp+=3; //affectation
                }
        }
        
        public boolean pasPaire(int id) {
+               ChercherMin.comp++; //test
                return ens_[id] == null;
        }
        
        public void add(int id, int val) {
+               ChercherMin.comp++; //affectation
                ens_[id].add(val); 
        }
 /*     
@@ -69,8 +84,12 @@ public class ClasseUnion {
        }
        
        public int classeVal(int i) {
+               ChercherMin.comp++; //test
                for (Coll c:ens_) {
+                       ChercherMin.comp++; // affectation
+                       ChercherMin.comp++; // test
                        if (!c.empty()) {
+                               ChercherMin.comp++; // test
                                if (c.getEns().contains(i)) {
                                        return c.getId();
                                }
diff --git a/src/ClasseUnionCompress.java b/src/ClasseUnionCompress.java
new file mode 100644 (file)
index 0000000..e5fc527
--- /dev/null
@@ -0,0 +1,103 @@
+
+public class ClasseUnionCompress {
+       private int[] p_; // tableau de père
+       private Coll[] ens_; // ensemble de paire correspondant
+       
+       public ClasseUnionCompress(int t){
+               p_ = new int[t];
+               ChercherMin.comp++; //init
+               ens_ = new Coll[t];
+               ChercherMin.comp++; //init
+               
+               ChercherMin.comp+=2; // init + test
+               for (int i = 0; i < t; i++) {
+                       ChercherMin.comp+=2; // test + incrementation
+                       
+                       p_[i] = -1;
+                       ChercherMin.comp++;
+                       ens_[i] = new Coll(i);
+                       ChercherMin.comp++;
+               }
+               
+       }
+       
+       public int classe(int i) {
+               ChercherMin.comp++; // test
+               if (p_[i] == -1) {
+                       return i;
+               }
+               else {
+                       ChercherMin.comp+=2; // affectation
+                       int cl = classe(p_[i]);
+                       p_[i] = cl;
+                       return cl;
+               }
+       }
+       
+       public void union(int a, int b) {
+               ChercherMin.comp++; // test
+               if (classe(a) != classe(b)) {
+                       p_[b] = a;
+
+                       ens_[a].add(ens_[b]);
+                       ens_[b].resetEns();
+                       ChercherMin.comp+=3; //affectation
+               }
+       }
+       
+       public boolean pasPaire(int id) {
+               ChercherMin.comp++; //test
+               return ens_[id] == null;
+       }
+       
+       public void add(int id, int val) {
+               ChercherMin.comp++; //affectation
+               ens_[id].add(val); 
+       }
+/*     
+       public void creer(int i) {
+               ens_[i] = new Coll(i);
+       }
+*/     
+       public Coll[] getColl() {
+               return ens_;
+       }
+       
+       public void toStr()
+       {
+               for (int i = 0; i < p_.length;i++)
+                       System.out.print(i + ":" + p_[i] + "    ");
+               System.out.println();
+       }
+       
+       public String toString() {
+               String s = "{";
+               for (Coll c : ens_){
+                       if (!c.empty()) {
+                               s+=c;
+                               s+=",";
+                       }
+               }
+               
+               if (s.charAt(s.length()-1) == ',')
+                       s = s.substring(0,s.length()-1);
+               
+               s+="}";
+               return s;
+       }
+       
+       public int classeVal(int i) {
+               ChercherMin.comp++; //test
+               for (Coll c:ens_) {
+                       ChercherMin.comp++; // affectation
+                       ChercherMin.comp++; // test
+                       if (!c.empty()) {
+                               ChercherMin.comp++; // test
+                               if (c.getEns().contains(i)) {
+                                       return c.getId();
+                               }
+                       }
+               }
+               return -1;
+       }
+}
index 3253b33..66fe982 100644 (file)
@@ -11,8 +11,8 @@ public class Paire
 \r
        public Paire(int a, int b)\r
        {\r
-               this.a = a;\r
-               this.b = b;\r
+               this.a = (a<b)?a:b;\r
+               this.b = (a<b)?b:a;\r
        }\r
 \r
        public Paire(int a)\r
index 8f98b65..69a3ca6 100644 (file)
@@ -36,6 +36,15 @@ public class Permutation
                }
                return elts[i-1];
        }
+       
+       public int indexOf(int val) {
+               for (int i = 0; i < elts.length; i++) {
+                       if (elts[i] == val) {
+                               return i+1;
+                       }
+               }
+               return -1;
+       }
 
        public void setN(int n)
        {
index d4aef8d..5e57a35 100644 (file)
@@ -5,9 +5,7 @@ import java.util.Scanner;
 \r
 public class Prog\r
 {\r
-       //final static String pathPermutation="/comptes/E115567R/L3/Algorithmique & Structures de donn�es 3/TP/Projet/A&SD3-Projet/permutations.txt";\r
-       //final static String pathPermutation="C:/MyFiles/Prog/Projet Algo/IntervallesCommuns/permutations.txt";\r
-       final static String pathPermutation="../permutations.txt";\r
+       final static String pathPermutation="./permutations.txt";\r
        public static Permutation load(int l)\r
        {\r
                int n;\r
@@ -79,7 +77,7 @@ public class Prog
 \r
        public static void main(String[] args)\r
        {\r
-               /*\r
+               \r
                ArrayList<Permutation> p = loadAll();\r
 \r
                for (int i = 0; i < p.size(); ++i)\r
@@ -87,8 +85,31 @@ public class Prog
                        System.out.println(p.get(i).eltsToString());\r
                        p.get(i).chercherMinPremier();\r
                        System.out.println(p.get(i).minsToString());\r
+                       ArrayList<Paire> paires = new ArrayList<Paire>();\r
+                       \r
+                       for (int j = 1; j < p.get(i).getN(); j++) {\r
+                               paires.add(new Paire(p.get(i).indexOf(j),p.get(i).indexOf(j+1)));\r
+                       }\r
+                       \r
+                       int[] minsCompress;\r
+                       minsCompress = ChercherMin.CURang(p.get(i),paires);\r
+                       System.out.print("(");\r
+                       for (int j : minsCompress) {\r
+                               System.out.print(" "+j+" ");\r
+                       }\r
+                       System.out.println(")");\r
+                       \r
+                       System.out.println("**************************");\r
+                       \r
+                       minsCompress = ChercherMin.CURangCompress(p.get(i),paires);\r
+                       System.out.print("(");\r
+                       for (int j : minsCompress) {\r
+                               System.out.print(" "+j+" ");\r
+                       }\r
+                       System.out.println(")");\r
                }\r
-               */\r
+               \r
+               /*\r
                Permutation p = load(1);\r
                ArrayList<Paire> paires = new ArrayList<Paire>();\r
                paires.add(new Paire(1,2));\r
@@ -96,6 +117,10 @@ public class Prog
                paires.add(new Paire(1,4));\r
                System.out.println(p.eltsToString());\r
                ChercherMin.CURang(p,paires);\r
+               System.out.println("**************************");\r
+               ChercherMin.CURangCompress(p,paires);\r
+               */\r
+               \r
        }\r
 }\r
 \r