Implement algo ChercherMinCURang
authorDralagen <dralagen@dralagen.fr>
Tue, 3 Dec 2013 08:17:34 +0000 (09:17 +0100)
committerDralagen <dralagen@dralagen.fr>
Tue, 3 Dec 2013 08:30:31 +0000 (09:30 +0100)
permutations.txt
src/ChercherMin.java [new file with mode: 0644]
src/ClasseUnion.java
src/Coll.java [new file with mode: 0644]
src/CollPaires.java [deleted file]
src/Paire.java
src/Permutation.java
src/Prog.java

index 5df665e..1276588 100755 (executable)
@@ -1,8 +1,9 @@
+8 (6 2 3 5 4 7 1 8)
 2 (1 2)
 3 (3 2 1)
 4 (2 4 1 3)
 5 (3 5 2 4 1)
 6 (1 3 6 4 5 2)
 7 (4 5 6 2 1 3 7)
-8 (5 4 3 8 6 7 2 3)
-9 (3 4 8 6 1 5 2 7 9)
+8 (5 4 3 8 6 7 2 1)
+9 (5 8 1 3 2 4 9 7 6)
diff --git a/src/ChercherMin.java b/src/ChercherMin.java
new file mode 100644 (file)
index 0000000..f814a07
--- /dev/null
@@ -0,0 +1,39 @@
+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) {
+               /*
+                * Coll : ({},id)
+                * 
+                */
+               ClasseUnion C = new ClasseUnion(P.getN()+2);
+               
+               
+               for (int h = 0; h <= P.getN(); h++) {
+                       int ph = P.getElts(h);
+                       for(Coll c : C.getColl()){
+                               if (!c.empty()) {
+                                       if (c.getId() >= ph) {
+                                               C.union(ph,c.getId());
+                                       }
+                               }
+                       }
+                       
+                       //C.creer(ph);
+                       C.add(ph,h);
+                       
+                       for(Paire pr : R) {
+                               if (h == pr.getB()) {
+                                       
+                                       System.out.println("Min("+pr.getA()+","+pr.getB()+") = " +C.classeVal(pr.getA()));
+                               }
+                       }
+                       System.out.println(C);
+               }
+       }
+}
index 16a23f2..3c30b45 100644 (file)
@@ -1,12 +1,16 @@
 
 public class ClasseUnion {
-       private int[] p_;
+       private int[] p_; // tableau de père
+       private Coll[] ens_; // ensemble de paire correspondant
        
        public ClasseUnion(int t){
                p_ = new int[t];
+               ens_ = new Coll[t];
                for (int i = 0; i < t; i++) {
                        p_[i] = -1;
+                       ens_[i] = new Coll(i);
                }
+               
        }
        
        public int classe(int i) {
@@ -17,24 +21,61 @@ public class ClasseUnion {
        }
        
        public void union(int a, int b) {
-               int pa=0,pb=0;
-               while (p_[a] != -1) {
-                       pa++;
-                       a = p_[a];
+               if (classe(a) != classe(b)) {
+                       p_[b] = a;
+
+                       ens_[a].add(ens_[b]);
+                       ens_[b].resetEns();
                }
-               
-               while (p_[b] != -1) {
-                       pb++;
-                       b = p_[b];
+       }
+       
+       public boolean pasPaire(int id) {
+               return ens_[id] == null;
+       }
+       
+       public void add(int id, int val) {
+               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 (a != b) {
-                       if (pa < pb) {
-                               p_[a] = b;
-                       }
-                       else {
-                               p_[b] = a;
+               if (s.charAt(s.length()-1) == ',')
+                       s = s.substring(0,s.length()-1);
+               
+               s+="}";
+               return s;
+       }
+       
+       public int classeVal(int i) {
+               for (Coll c:ens_) {
+                       if (!c.empty()) {
+                               if (c.getEns().contains(i)) {
+                                       return c.getId();
+                               }
                        }
                }
+               return -1;
        }
 }
diff --git a/src/Coll.java b/src/Coll.java
new file mode 100644 (file)
index 0000000..da950ac
--- /dev/null
@@ -0,0 +1,56 @@
+import java.util.Iterator;
+import java.util.Vector;
+
+
+public class Coll {
+       private Vector<Integer> ens_;
+       private int id_;
+       
+       public Coll(int id) {
+               id_ = id;
+               ens_ = new Vector<Integer>();
+       }
+       
+       public Coll(int id, Vector<Integer> ens) {
+               id_ = id;
+               ens_ = ens;
+       }
+       
+       public int getId() {
+               return id_;
+       }
+       
+       public Vector<Integer> getEns() {
+               return ens_;
+       }
+       
+       public void resetEns() {
+               ens_ = new Vector<Integer>();
+       }
+       
+       public void add(int val) {
+               ens_.add(val);
+       }
+       public void add(Coll val) {
+               ens_.addAll(val.getEns());
+       }
+       
+       public String toString() {
+               String s = "({";
+               for (Iterator<Integer> it = ens_.iterator(); it.hasNext();) {
+                       int i = it.next();
+                       s+=i;
+                       if (it.hasNext()) {
+                               s+=", ";
+                       }
+               }
+               s+="},";
+               s+=id_;
+               s+=")";
+               return s;
+       }
+       
+       public boolean empty() {
+               return ens_.size() == 0;
+       }
+}
diff --git a/src/CollPaires.java b/src/CollPaires.java
deleted file mode 100644 (file)
index 94f8c12..0000000
+++ /dev/null
@@ -1,39 +0,0 @@
-import java.util.Vector;
-
-public class CollPaires
-{
-       private Vector<Paire> c;
-       private Vector<Integer> ids;
-       
-       public CollPaires()
-       {
-               c = new Vector<Paire>();
-               ids = new Vector<Integer>();
-       }
-       
-       public CollPaires(Vector<Paire> c, Vector<Integer> ids)
-       {
-               this.c = c;
-               this.ids = ids;
-       }
-
-       public Vector<Paire> getC()
-       {
-               return c;
-       }
-
-       public void setC(Vector<Paire> c)
-       {
-               this.c = c;
-       }
-
-       public Vector<Integer> getIds()
-       {
-               return ids;
-       }
-
-       public void setIds(Vector<Integer> ids)
-       {
-               this.ids = ids;
-       }
-}
index 5ca62c5..3253b33 100644 (file)
@@ -1,44 +1,44 @@
-
-public class Paire
-{
-       private int a;
-       private int b;
-       
-       public Paire()
-       {
-               a = 0;
-               b = 0;
-       }
-       
-       public Paire(int a, int b)
-       {
-               this.a = a;
-               this.b = b;
-       }
-       
-       public Paire(int a)
-       {
-                       this.a = a;
-                       b = a + 1;
-       }
-       
-       public int getA()
-       {
-               return a;
-       }
-       
-       public int getB()
-       {
-               return b;
-       }
-       
-       public void setA(int a)
-       {
-               this.a = a;
-       }
-       
-       public void setB(int b)
-       {
-               this.b = b;
-       }
-}
+public class Paire\r
+{\r
+       private int a;\r
+       private int b;\r
+\r
+       public Paire()\r
+       {\r
+               a = 0;  // on considère que a est l'identifiant\r
+               b = 1;\r
+       }\r
+\r
+       public Paire(int a, int b)\r
+       {\r
+               this.a = a;\r
+               this.b = b;\r
+       }\r
+\r
+       public Paire(int a)\r
+       {\r
+               this.a = a;\r
+               b = a + 1;\r
+       }\r
+\r
+       public int getA()\r
+       {\r
+               return a;\r
+       }\r
+\r
+       public int getB()\r
+       {\r
+               return b;\r
+       }\r
+\r
+       public void setA(int a)\r
+       {\r
+               this.a = a;\r
+       }\r
+\r
+       public void setB(int b)\r
+       {\r
+               this.b = b;\r
+       }\r
+}\r
+\r
index beb91cd..8f98b65 100644 (file)
@@ -1,11 +1,8 @@
-import java.util.*;
-
-
 public class Permutation
 {
-       private int n;
-       private int elts[];
-       private int mins[];
+       private int n;                  // nombre d'éléments
+       private int elts[];             // éléments
+       private int mins[];             // minimums des paires
 
 
        public Permutation()
@@ -32,6 +29,14 @@ public class Permutation
                return elts;
        }
 
+       public int getElts(int i)
+       {
+               if (i == 0) {
+                       return n+1;
+               }
+               return elts[i-1];
+       }
+
        public void setN(int n)
        {
                this.n = n;
@@ -44,9 +49,9 @@ public class Permutation
                this.elts = elts;
        }
 
-       public void chercherMin()
+       public void chercherMinPremier()
        {
-               int j, t, min;
+               int j, t;
                int idMin,idMax;
                int idVMin,idVMax;
                for (t = 1; t < n ;t++)
@@ -98,11 +103,10 @@ public class Permutation
        public String minsToString()
        {
                String s = "(";
-    for(int i : mins) {
-      s+=" "+i+" ";
-    }
-    s+=")";
-    return s;
+               for(int i : mins)
+                       s += " " + i + " ";
+               s+=")";
+               return s;
        }
 
        public void genRandom()
@@ -119,3 +123,4 @@ public class Permutation
                }
        }
 }
+
index 9ff0524..d4aef8d 100644 (file)
-import java.io.FileReader;
-import java.util.ArrayList;
-import java.util.Scanner;
-
-
-public class Prog
-{
-       final static String pathPermutation="permutations.txt";
-       public static Permutation load(int l)
-       {
-               int n;
-               int[] elts;
-               Permutation p = null;
-               try
-               {
-                       Scanner sc = new Scanner(new FileReader(pathPermutation));
-                       for (int i=1; i < l; i++)
-                       {
-                               if (sc.hasNextLine())
-                                       sc.nextLine();
-                       }
-                       if (sc.hasNextLine()) {
-                               n = sc.nextInt();
-                               elts = new int[n];
-                               String buff;
-                               for (int i = 0; i < n ; i++)
-                               {
-                                       buff = sc.next();
-                                       buff = buff.replace(")","");
-                                       buff = buff.replace("(","");
-                                       elts[i] = Integer.parseInt(buff);
-                               }
-                               p = new Permutation(n,elts);
-                       }
-                       sc.close();
-               } catch (Exception e)
-               {
-                       e.printStackTrace();
-               }
-               return p;
-       }
-
-       public static Permutation load() {
-               return load(1);
-       }
-       public static ArrayList<Permutation> loadAll()
-       {
-               ArrayList<Permutation> p = new ArrayList<Permutation>();
-               try
-               {
-                       int n;
-                       int elts[];
-                       Scanner sc = new Scanner(new FileReader(pathPermutation));
-                       while (sc.hasNextLine()) {
-                               if (sc.hasNextInt()){
-                                       n = sc.nextInt();
-                                       elts = new int[n];
-                                       String buff;
-                                       for (int i = 0; i < n ; i++)
-                                       {
-                                               buff = sc.next();
-                                               buff = buff.replace(")","");
-                                               buff = buff.replace("(","");
-                                               elts[i] = Integer.parseInt(buff);
-                                       }
-                                       p.add(new Permutation(n,elts));
-                               }
-                               sc.nextLine();
-                       }
-                       sc.close();
-               } catch (Exception e)
-               {
-                       e.printStackTrace();
-               }
-               return p;
-       }
-
-       public static void main(String[] args)
-       {
-               ArrayList<Permutation> p = loadAll();
-               for (int i = 0; i < p.size(); ++i){
-                       System.out.println(p.get(i).eltsToString());
-                       p.get(i).chercherMin();
-                       System.out.println(p.get(i).minsToString());
-               }
-       }
-}
+import java.io.FileReader;\r
+import java.util.ArrayList;\r
+import java.util.Scanner;\r
+\r
+\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
+       public static Permutation load(int l)\r
+       {\r
+               int n;\r
+               int[] elts;\r
+               Permutation p = null;\r
+               try\r
+               {\r
+                       Scanner sc = new Scanner(new FileReader(pathPermutation));\r
+                       for (int i=1; i < l; i++)\r
+                       {\r
+                               if (sc.hasNextLine())\r
+                                       sc.nextLine();\r
+                       }\r
+                       if (sc.hasNextLine()) {\r
+                               n = sc.nextInt();\r
+                               elts = new int[n];\r
+                               String buff;\r
+                               for (int i = 0; i < n ; i++)\r
+                               {\r
+                                       buff = sc.next();\r
+                                       buff = buff.replace(")","");\r
+                                       buff = buff.replace("(","");\r
+                                       elts[i] = Integer.parseInt(buff);\r
+                               }\r
+                               p = new Permutation(n,elts);\r
+                       }\r
+                       sc.close();\r
+               } catch (Exception e)\r
+               {\r
+                       e.printStackTrace();\r
+               }\r
+               return p;\r
+       }\r
+\r
+       public static Permutation load() {\r
+               return load(1);\r
+       }\r
+       public static ArrayList<Permutation> loadAll()\r
+       {\r
+               ArrayList<Permutation> p = new ArrayList<Permutation>();\r
+               try\r
+               {\r
+                       int n;\r
+                       int elts[];\r
+                       Scanner sc = new Scanner(new FileReader(pathPermutation));\r
+                       while (sc.hasNextLine()) {\r
+                               if (sc.hasNextInt()){\r
+                                       n = sc.nextInt();\r
+                                       elts = new int[n];\r
+                                       String buff;\r
+                                       for (int i = 0; i < n ; i++)\r
+                                       {\r
+                                               buff = sc.next();\r
+                                               buff = buff.replace(")","");\r
+                                               buff = buff.replace("(","");\r
+                                               elts[i] = Integer.parseInt(buff);\r
+                                       }\r
+                                       p.add(new Permutation(n,elts));\r
+                               }\r
+                               sc.nextLine();\r
+                       }\r
+                       sc.close();\r
+               } catch (Exception e)\r
+               {\r
+                       e.printStackTrace();\r
+               }\r
+               return p;\r
+       }\r
+\r
+       public static void main(String[] args)\r
+       {\r
+               /*\r
+               ArrayList<Permutation> p = loadAll();\r
+\r
+               for (int i = 0; i < p.size(); ++i)\r
+               {\r
+                       System.out.println(p.get(i).eltsToString());\r
+                       p.get(i).chercherMinPremier();\r
+                       System.out.println(p.get(i).minsToString());\r
+               }\r
+               */\r
+               Permutation p = load(1);\r
+               ArrayList<Paire> paires = new ArrayList<Paire>();\r
+               paires.add(new Paire(1,2));\r
+               paires.add(new Paire(3,7));\r
+               paires.add(new Paire(1,4));\r
+               System.out.println(p.eltsToString());\r
+               ChercherMin.CURang(p,paires);\r
+       }\r
+}\r
+\r