Combinatoire

Olympiades mathématiques, énigmes et défis
Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 04 Sep 2014, 23:12

en tout cas, par rapport à la matrice binaire et qu'on veut faire des packs de 1, ca correspond au terme seriation.

en particulier, on peut par exemple regarder un algo spectral pour seriation:
http://www.sandia.gov/~bahendr/papers/seriation.ps

(c'est assez bien expliqué et illustré)
Après je sais pas ce que ca donne au niveau des résultats, il faut que j'implémente pour voir...
la vie est une fête :)



Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 19:06

par Bramant52 » 05 Sep 2014, 01:26

fatal_error a écrit:en tout cas, par rapport à la matrice binaire et qu'on veut faire des packs de 1, ca correspond au terme seriation.

en particulier, on peut par exemple regarder un algo spectral pour seriation:
http://www.sandia.gov/~bahendr/papers/seriation.ps

(c'est assez bien expliqué et illustré)
Après je sais pas ce que ca donne au niveau des résultats, il faut que j'implémente pour voir...

Merci pour la reference sauf que dans mon cas la matrice est symetrique, carre et binaire.
J`ai trouve une astuce :
- partir d`une matrice carree, symetrique et binaire avec les 1 en diagonale et les 0 dans toutes les autres cases. Dans ce cas, la sous matrice a extraire serait un ensemble vide.
- introduire des 1 de maniere a construire une matrice dont on connait d`avance la taille de la sous-matrice a extraire. Passer de m=1 a m=n (m etant la taille de la sous matrice carre m*m).
- l`idee est de comparer cette matrice "fictive" a ma matrice de maniere a atteindre l`optimum.
l`optimum.
C`est encore confus dans ma tete je le precise mais je reste optimiste.

J`ai essaye de le faire sur une matrice reduite avec n=20, il y a des truce qui me chiffonnent et que je ne m`explique pas encore.
Je le fais manuellement sur Excel.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 05 Sep 2014, 10:10

la matrice étudiée dans le document est carrée symétrique et binaire (binaire étant facultatif):)
la vie est une fête :)

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 19:06

par Bramant52 » 05 Sep 2014, 14:11

fatal_error a écrit:la matrice étudiée dans le document est carrée symétrique et binaire (binaire étant facultatif):)

Merci.
J`ai un probleme avec le format ps et j`ai ouvert un pdf similaire sur la seriation.
Si c`est la cas alors l`algorithme donnerait theoriquement l`optimum.
Ce serait parfait.
Je suis l`algo loto et je pense avoir decouvert de nouvelles pistes.
Je le fais sur Excel et cela me prend beaucoup de temps mais l`avantage est que je suis en direct l`algo dans tous ses details. L`inconvenient est que je peux commettre des erreurs si la manipulation est longue.

1000 mercis a toi O grand Manitou.
Si je gagne le gros lot tu deviendras riche toi aussi. Je suis tres genereux avec les gens genereux.
Sur 100 millions d`euros, je te donnerai au minimum 20 millions car je pense aux milliers d`autres aussi. Avec 20 millions d`euros tu aurais la vie facile, tu pourrais passer ton temps a realiser tes projets et a rendre heureux tes proches.

lulubibi28
Membre Relatif
Messages: 240
Enregistré le: 10 Nov 2013, 13:18

par lulubibi28 » 05 Sep 2014, 14:32

C'est très rare de voir un jeu gratuit *.*

Par ailleurs , comment as-tu pu créer aussi vite une expression mathématique du loto ?

Entre parenthèses ,de nos jours , il y'a beaucoup de gens très riches mais pas instruits qui ne connaissent pas la valeur de l'argent , et donc ne contribue pas positivement à la société :triste:

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 19:06

par Bramant52 » 06 Sep 2014, 21:36

Salut,

Je reviens a cette histoire d`extraction de la plus grande sous matrice carre, binaire et symetrique.
Je ne sais pas combinen cela prendrait de temps mais voila mon algo :
- Une fois que l`on a la matrice binaire (1-0), symetrique et carree de depart, on le vecteur colonne 1 et on le multiplie par tous les vecteurs lignes (sauf le vecteur ligne 1). On aura des valeurs. On choisit uniquement les vecteurs qui ont le plus de 1 en commun. Il y en aura plusieurs.
- On reclasse la matrice de nouveau avec les plus hauts scores en tete des lignes et le reste apres.
- On recalcule les produits de chacun des vecteurs lignes avec les autres etc...
- On obtient une seconde iteration ...
Et ainsi de suite jusqu`a n`avoir qu`une seule solution : la plus large sous matrice (solution optimale).

Je previens que cela grossit au fur et a mesure, alors il faut trouver une astuce pour reduire l`espace en memoire.
Un essai avec n=10,11...jusqu`a 15 pourrait aider a traiter ce probleme (peut-etre?).

Ingrid55
Membre Relatif
Messages: 162
Enregistré le: 06 Juil 2014, 23:51

par Ingrid55 » 06 Sep 2014, 22:14

Si j'ai bien saisi , tu aimerais généraliser en fait ?
Mais quel est ton objectif réel avec l'extraction de la plus grande sous matrice carre, binaire et symétrique ?

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 19:06

par Bramant52 » 06 Sep 2014, 23:58

Ingrid55 a écrit:Si j'ai bien saisi , tu aimerais généraliser en fait ?
Mais quel est ton objectif réel avec l'extraction de la plus grande sous matrice carre, binaire et symétrique ?


Faut lire depuis le debut pour comprendre.
Le but est de trouver l`optimum.
Merci.

Ingrid55
Membre Relatif
Messages: 162
Enregistré le: 06 Juil 2014, 23:51

par Ingrid55 » 07 Sep 2014, 00:08

ok :euh: ( c vrai qu'il y'a 3 pages déjà)

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 08 Sep 2014, 15:42

bon... ca marche pas avec la seriation à priori parce que en cherchant le fieldvector, on tombe sur le vecteur propre de composantes toutes égales (car il y a le même nombre de 1 par ligne et colonne dans A), et du coup on récurse à l'infini dans la seconde branche de l'algorithme.

si on enlève cette première valeur propre, on est pas mal assujettis aux erreurs numériques et quand bien même (à 1e-4 près) la plus longue séquence de valeurs égales pour une instance (5,10) c'est pas 6 mais 3 ...
la vie est une fête :)

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 19:06

par Bramant52 » 08 Sep 2014, 16:28

fatal_error a écrit:bon... ca marche pas avec la seriation à priori parce que en cherchant le fieldvector, on tombe sur le vecteur propre de composantes toutes égales (car il y a le même nombre de 1 par ligne et colonne dans A), et du coup on récurse à l'infini dans la seconde branche de l'algorithme.

si on enlève cette première valeur propre, on est pas mal assujettis aux erreurs numériques et quand bien même (à 1e-4 près) la plus longue séquence de valeurs égales pour une instance (5,10) c'est pas 6 mais 3 ...


Merci pour la seriation.
J`abandonne un peu ce sujet pour l`instant car je pense arreter internet pour un moment.
J`ai plus important a faire.

Merci pour tout.

Ps : tu m`as aide a voir plus clair dans ce que je cherche. 1000 mercis.
Je reviendrai.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 27 Déc 2014, 18:31

je up cette discussion..

trouver une sous matrice composée que de 1, ca revient à trouver le maximum clique du graphe associé.
sur le net, vraisemblablement, ca se fait en exponentiel, mais il existe des algo approximant, j'essaie d'en trouver un...

edit: trouvé : aco-dls-clique
qui est assez récent et qui dépote pas mal :)
sur une instance 3 5 15 (15 elem, combi de taille 5, au plus deux elem en commun), je passe de 29 (avec mon algo basique) à 42...

Génrer le dimac
Code: Tout sélectionner
#include
#include
#include
#include
#include
#include
#include
#include
#include


class Timer {
  private:
    unsigned long begTime;
  public:
    void start() {
      begTime = clock();
    }

    unsigned long elapsedTime() {
      return ((unsigned long) clock() - begTime) / CLOCKS_PER_SEC;
    }

    bool isTimeout(unsigned long seconds) {
      return seconds >= elapsedTime();
    }
};
struct Params{
  size_t k;
  size_t p;
  size_t n;
  std::string toString()const{
    std::stringstream oss;
    oss Container;
  Comb(){}
  Comb(size_t n):_n(n), _v(n,0){}
  std::string stringify() const{
    std::stringstream oss;
    for(size_t i=0; i= max){
          return false;
        }
      }
    }
    return true;
  }
  void insert(size_t i){
    _v[i] = 1;
  }
protected: 
  Container _v;
  size_t _n;
};
struct Edge{
  const Comb* _c1;
  const Comb* _c2;
  Edge(const Comb* c1, const Comb* c2):_c1(c1), _c2(c2){}
  const Comb* beg()const{return _c1;}
  const Comb* end()const{return _c2;}
};
class Graph{
public:
  void addEdge(const Edge& e){
    _s.push_back(e);
  }
  void store(const Comb* c){
    size_t size = _m.size()+1;
    _m[c] = size;
  }
  void writeDimac(const std::string& fName)const{
    std::ofstream out(fName.c_str());
    std::stringstream oss;
    for(auto it = _s.begin(); it!=_s.end(); ++it){
      oss beg())->second end())->second second first->stringify() MyMap;
  MyMap _m;
  std::deque _s;
};
Params handleInput(int argc, char* argv[]){
  if(argc combinatorial(size_t k, size_t n){
  std::vector v(n);
  std::vector ol(C(k,n));
  std::fill(v.begin() + n - k, v.end(), true);
  size_t z = 0;
  do {
      Comb combination(n);
      for (size_t i = 0; i  &combs){
  Graph g;
  Timer t;
  std::coutcompatible(*it2, k)){
        g.addEdge(Edge(&*it, &*it2));
      }
    }
  }
  std::cout<<"elapsed "<<t.elapsedTime()<<std::endl;
  return g;
}
int main(int argc, char* argv[]){
  try{
    const auto &params = handleInput(argc, argv);
    const auto &combs = combinatorial(params.p, params.n);
    std::cout<<"combis : "<<combs.size()<<std::endl;
    Graph g = buildGraph(params.k, combs);
    std::cout<<"built"<<std::endl;
    g.writeDimac("./output.txt");
    g.writeCombis("./graph.txt");
   
  }catch(const std::string &e){
    std::cout<<e<<std::endl;
    std::cout<<"expects ./exe k p n \n";
    std::cout<<"where \n";
    std::cout<<"\t k : maximum size of intersecting set of two random combination (excluded) \n";
    std::cout<<"\t p : size of combination taken from elements \n";
    std::cout<<"\t n : number of elements"<<std::endl;
  }
  return 0;
}


Afficher les solutions
Code: Tout sélectionner
#!/home/gogol/soft/io.js/bin/bin/node
var exec = require('child_process').exec;
var fs = require('fs');
function Buf(size, onComplete){
  this.size = size;
  this.onComplete = onComplete;
  this.s = '';
}
Buf.prototype.fill = function(data){
  this.s += data;
  if(this.s.length == this.size){
    this.onComplete();
  }
}
Buf.prototype.empty = function(){
  this.s = '';
}
function printComb(line, graph){
  var arr = line.split('').map(function(digit, idx){
    if(digit=='0'){
      return ;
    }
    idx = line.length - 1 - idx; //bit vector output by aco-dls-clique is read from right to left
    return (idx+1)+':'+graph[idx+1];
  }).filter(function(x){
    return x && x.length
  })
  console.log('Solution : '+line+'\n'+'length : '+arr.length);
  console.log(arr.join('\n')+'\n');
}
exec('./exe 3 5 15', function(err, stdout, stderr){
  var combiMap = {}
  console.log('reading graph');
  fs.readFile('./graph.txt', function(err, data){
    combiMap = JSON.parse(data.toString());
    var cmd = ['cd somePath/aco-dls-clique/src/cpp'];
    cmd.push('./local-go somePath/cliques/output.txt 1 100000 5');
    var buf = new Buf(Object.keys(combiMap).length, function(){
      printComb(buf.s, combiMap);
      buf.empty();
    });
    console.log('running '+cmd)
    var child = exec(cmd.join(' && '));
    child.stdout.on('data', function(data){
      data.split('\n').filter(function(line){
        return line.match(/^[01]+$/);
      }).forEach(function(dataQuantum){
        buf.fill(dataQuantum);
      });
    });
  });
});


résult: (pas encore fini à l'heure actuelle)
Code: Tout sélectionner
2992:8,9,12,13,14
2894:6,7,9,10,12
2888:6,7,8,11,13
2727:4,8,10,11,12
2609:4,5,9,10,14
2567:4,5,6,12,13
2400:3,5,9,11,12
2388:3,5,8,10,13
2338:3,5,6,7,14
2330:3,4,11,13,14
2276:3,4,7,8,9
2198:2,9,10,11,13
2150:2,7,8,10,14
2139:2,6,11,12,14
2009:2,5,6,8,9
1893:2,4,5,7,11
1844:2,3,7,12,13
1729:2,3,4,6,10
1642:1,6,10,13,14
1567:1,5,8,11,14
1544:1,5,7,9,13
1470:1,4,7,12,14
1437:1,4,6,9,11
1342:1,3,7,10,11
1313:1,3,6,8,12
1129:1,2,5,10,12
1085:1,2,4,8,13
1046:1,2,3,9,14
953:0,7,9,11,14
823:0,5,7,8,12
810:0,5,6,10,11
749:0,4,7,10,13
720:0,4,6,8,14
666:0,3,10,12,14
604:0,3,6,9,13
422:0,2,5,13,14
374:0,2,4,9,12
323:0,2,3,8,11
283:0,1,11,12,13
252:0,1,8,9,10
2:0,1,2,6,7
1:0,1,3,4,5


bref, faut faire confiance aux chercheurs, du coup, l'information qui est perdue, c'est qu'on sait qu'on génère nos permutations, (alors que aco-dls ne prend qu'un graphe quelconque en entrée), du coup, faudrait arriver à se servir de ca (un peu comme Groucho l'a fait avec F_x ou plus faiblement en trouvant des cut gratuits)...
la vie est une fête :)

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 04 Jan 2015, 15:49

Salut,

Je viens de verifier les 42 combinaisons cela marche.
Je ne sais toujours pas comment fonctionne ton algorithme.
Pour 18 cela donne quoi?

Merci.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 04 Jan 2015, 16:43

hello,

moi non plus, j'ai pas pris la peine de lire, l'algo est pas de moi
c'est pris de githug aco-dls (dynamic local search)
le papier peut etre trouvé là : http://arxiv.org/pdf/1109.5717.pdf

pour 18 j'ai trouvé 69 en une heure et 68 en dix minutes
la vie est une fête :)

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 04 Jan 2015, 16:46

fatal_error a écrit:hello,

moi non plus, j'ai pas pris la peine de lire, l'algo est pas de moi
c'est pris de githug aco-dls (dynamic local search)
le papier peut etre trouvé là : http://arxiv.org/pdf/1109.5717.pdf

pour 18 j'ai trouvé 69 en une heure et 68 en dix minutes

Bravo!!!
Peux-tu publier les 69 s`il te plait.
Mon record est 68.
25 cela donne quoi?
Le 25 m`interesse particulierement.

Merci

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 04 Jan 2015, 16:56

j'ai pas pris la peine de noter le 69 et le 3 5 25 me fait planter (...) la bécane :marteau:
la vie est une fête :)

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 04 Jan 2015, 17:05

fatal_error a écrit:j'ai pas pris la peine de noter le 69 et le 3 5 25 me fait planter (...) la bécane :marteau:

Je pense qu`il y a un moyen de ne pas faire planter la becane en revoyant ton programme.
Meme a n=100 cela marcherait.
J`y reflechis.
Tu peux aussi y reflechir bien sur, tu connais ton programme mieux que moi :hein:

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 04 Jan 2015, 17:14

oui c'est une évidence, mais ca ne serait qu'une optimisation "technique".
il vaut mieux trouver un algorithme plus efficace.

si tu veux quand même perdre du temps à optimiser le code, tu peux te baser sur
Code: Tout sélectionner
#include
#include
#include
#include
#include
#include
#include
#include
#include

#include
#include "local.hpp"
#include
#define MAX_THREADS 8
class Timer {
  private:
    unsigned long begTime;
    std::string _s;
  public:
    void start(const std::string& s) {
      std::cout= elapsedTime();
    }
};
struct Params{
  size_t k;
  size_t p;
  size_t n;

  Params():spd(1),steps(100000),cons(5){}
  size_t spd;
  size_t steps;
  size_t cons;
  std::string toString()const{
    std::stringstream oss;
    oss Container;
  Comb(){}
  Comb(size_t n, size_t idx):_n(n), _v(n,0), _idx(idx){}
  std::string stringify() const{
    std::stringstream oss;
    for(size_t i=0; i= max){
          return false;
        }
      }
    }
    return true;
  }
  size_t idx()const{return _idx;}
  void insert(size_t i){
    _v[i] = 1;
  }
protected: 
  Container _v;
  size_t _n;
  size_t _idx;
};
struct Edge{
  const Comb* _c1;
  const Comb* _c2;
  Edge(const Comb* c1, const Comb* c2):_c1(c1), _c2(c2){}
  const Comb* beg()const{return _c1;}
  const Comb* end()const{return _c2;}
};
class Graph{
  typedef std::vector Container;
public:
  Graph(const Container* c):_m(c){}
  void addEdge(const Edge& e){
    _s.push_back(e);
  }
  void writeDimac(const std::string& fName)const{
    std::ofstream out(fName.c_str());
    std::stringstream oss;
    Timer t;
    t.start("foor loop");
    for(auto it = _s.begin(); it!=_s.end(); ++it){
      oss beg()->idx();
      oss end()->idx() size()size(), _s.size());
    for(auto it = _s.begin(); it!=_s.end(); ++it){
      g->add_edge(it->beg()->idx()-1, it->end()->idx()-1);
    }
    return g;
  }
  void writeCombis(const std::string& fName)const{
    std::ofstream out(fName.c_str());
    std::stringstream oss;
    for(auto it = _m->begin(); it!=_m->end(); ++it){
      oss idx() stringify() _s;
};
Params handleInput(int argc, char* argv[]){
  if(argc combinatorial(size_t k, size_t n){
  std::vector v(n);
  std::vector ol(C(k,n));
  std::fill(v.begin() + n - k, v.end(), true);
  size_t z = 0;
  do {
      Comb* combination = new Comb(n, z+1);
      for (size_t i = 0; i insert(i);
          }
      }
      ol[z] = combination;
      z++;
  } while (std::next_permutation(v.begin(), v.end()));
  return ol;
}
Graph buildGraph(size_t k, const std::vector &combs){
  Graph g(&combs);
  Timer t;
  t.start("building graph");
  auto p_comb = combs[0];
  std::vector candidates;
  candidates.reserve(combs.size());
  for(auto it2 = combs.begin()+1; it2!=combs.end(); ++it2){
    if(p_comb->compatible(**it2, k)){
      g.addEdge(Edge(p_comb, *it2));
      candidates.push_back(*it2);
    }
  }
  for(auto it = candidates.begin(); it!=candidates.end(); ++it){
    for(auto it2 = it+1; it2!=candidates.end(); ++it2){
      if((*it)->compatible(**it2, k)){
        g.addEdge(Edge(*it, *it2));
      }
    }
  }
  t.stop();
  return g;
}
void go(const Graph& graph, const Params &p){
  graph_t *g = graph.getGraph_t();

  boost::thread threads[MAX_THREADS];
  DLS *dls = new DLS[MAX_THREADS];
  double start = (double)clock()/CLOCKS_PER_SEC;
  std::cout n, dls);
  }
  std::cout  "  " << bests.size() << std::endl;
  std::cout << "Primer mejor en " << bestFirst - start << std::endl;
  delete g;
}
int main(int argc, char* argv[]){
  try{
    const auto &params = handleInput(argc, argv);
    const auto &combs = combinatorial(params.p, params.n);
    std::cout<<"combis : "<<combs.size()<<std::endl;
    Graph g = buildGraph(params.k, combs);
    std::cout<<"built"<<std::endl;
    Timer t;
    t.start("write combis");
    g.writeCombis("./graph.txt");
    t.stop();
    std::cout<<"combi ready"<<std::endl;
    go(g, params);
    for(auto comb: combs){
      delete comb;
    }
  }catch(const std::string &e){
    std::cout<<e<<std::endl;
    std::cout<<"expects ./exe k p n \n";
    std::cout<<"where \n";
    std::cout<<"\t k : maximum size of intersecting set of two random combination (excluded) \n";
    std::cout<<"\t p : size of combination taken from elements \n";
    std::cout<<"\t n : number of elements"<<std::endl;
  }
  return 0;
}

il y a quelques optim (changement des data structures, etc)

le reste c'est le code de dls à revoir
la vie est une fête :)

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 04 Jan 2015, 17:21

Je pensais a autre chose.
On peut reduire la matrice au fur et a mesure que l`on avance.
Je faisais manuellement.
Et la matrice se reduit considerablement.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 04 Jan 2015, 17:24

En plus si tu prends du recul et que tu analyses tes matrices extraites, certaines sont extraites a partir d`autres (pas toutes bien sur).

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite