Combinatoire

Olympiades mathématiques, énigmes et défis
Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 19:06

par Bramant52 » 28 Aoû 2014, 22:15

nodjim a écrit:En fait ce n'est pas tout a fait C(18,3)/C(5,3), il y a un facteur réducteur du dénominateur, je tâcherai de l'expliquer plus tard.


Il y a 816 triplets. 5 numeros couvrent 10 triplets.
Donc, au plus peut-on creer 81 quintuplets.
Ca, c`est la majoration elementaire, evidente.
Avec 68 quintuplets je remplis mes conditions (au plus 2 en commun).
Je couvre de fait 680 triplets.
Reste 136 triplets non couverts.
Maintenant comment savoir que l`on a atteint l`optimum?
Je crois le savoir mais reste a confirmer



nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 29 Aoû 2014, 19:56

Pas tout à fait. Prends le cas n=15. Ordonne tes triplets dans l'ordre croissant (1,4 9 au lieu de 4,1,9) et pars de ce principe pour ordonner aussi les quintets que tu crées: Les triplets finissant par 14 ou 15 n'ont pas de solutions !

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

par fatal_error » 29 Aoû 2014, 20:50

bj,

alors de mon côté j'ai laissé tomber les matrices d'adjacence parce que c'est trop long.
Voilà un algo plus rapide (mais qui donne malheureusement pas l'optimal):
pour 5,18
Code: Tout sélectionner
g++ -g -o main.o -c main.cpp -W -Wall -ansi -pedantic
g++ -g -o combi main.o
0,1,2,3,4
0,1,5,6,7
0,1,8,9,10
0,1,11,12,13
0,1,14,15,16
0,2,5,8,11
0,2,6,9,12
0,2,7,10,13
0,3,5,9,13
0,3,6,8,14
0,3,7,11,15
0,3,10,12,16
0,4,5,10,14
0,4,6,11,16
0,4,7,8,12
0,4,9,15,17
0,8,13,16,17
1,2,5,9,14
1,2,6,8,13
1,2,7,11,16
1,2,10,12,15
1,3,5,8,12
1,3,6,9,11
1,3,7,10,14
1,3,13,15,17
1,4,5,11,15
1,4,6,10,17
1,4,7,9,13
1,5,10,13,16
1,8,11,14,17
1,9,12,16,17
2,3,5,6,10
2,3,7,8,9
2,3,11,12,14
2,4,5,7,17
2,4,6,14,15
2,4,8,10,16
2,9,10,11,17
2,9,13,15,16
3,4,6,12,13
3,4,9,14,16
3,5,11,16,17
3,8,10,11,13
4,5,6,8,9
5,6,11,13,14
5,6,12,15,16
5,7,8,10,15
5,7,9,11,12
6,7,9,10,16
6,7,12,14,17
8,9,12,13,14

=======
count : 51 (comme le pastis)
0


le code associé:
Code: Tout sélectionner
#include
#include
#include
#include
#include
#include
#include

template
std::string setToString(const storeTuple& outList){
  std::stringstream oss;
  for(typename storeTuple::const_iterator it=outList.begin();
      it!=outList.end(); ++it){
    osstoString() storeType;
  typedef typename storeType::const_iterator const_iterator;
  Tuple(){}
  Tuple(size_t a, size_t b, size_t c){
    _v.insert(a);
    _v.insert(b);
    _v.insert(c);
  }
  Tuple(size_t a, size_t b, size_t c, size_t d){
    _v.insert(a);
    _v.insert(b);
    _v.insert(c);
    _v.insert(d);
  }
  Tuple(size_t a, size_t b, size_t c, size_t d, size_t e){
    _v.insert(a);
    _v.insert(b);
    _v.insert(c);
    _v.insert(d);
    _v.insert(e);
  }
  size_t size()const{
    return _v.size();
  }
  bool operator==(const Tuple &other)const{
    if(_v.size()!=other._v.size()){
      return false;
    }
    for(typename storeType::const_iterator it=begin(); it!=end();
        ++it){
      if(other._v.find(*it)==other._v.end()){
        return false;
      }
    }
    return true;
  }
  Tuple operator+(const Tuple &other)const{
    Tuple v;
    v._v.insert(_v.begin(), _v.end());
    v._v.insert(other._v.begin(), other._v.end());
    return v;
  }
  std::string toString ()const{
    std::stringstream oss;
    for(typename storeType::const_iterator it=_v.begin();
      it!=_v.end();++it){
        oss _v;
};
template
void combinatorial(T& ol, size_t k, size_t n){
  std::vector v(n);
  std::fill(v.begin() + n - k, v.end(), true);
  do {
      typename T::mapped_type::value_type tuple;
      for (size_t i = 0; i  > storeType;
  typedef typename storeType::mapped_type mapped_type;
  typedef typename storeType::key_type key_type;
  typedef typename storeType::const_iterator const_iterator;
  bool empty()const{
    return size()==0;
  }
  typename storeType::const_iterator begin()const{
    return _v.begin();
  }
  typename storeType::const_iterator end()const{
    return _v.end();
  }
  const typename storeType::mapped_type& front()const{
    return _v.begin()->second;
  }
  typename storeType::mapped_type& operator[](
      const storeType::key_type &key){
    return _v[key];
  }
  typename storeType::const_iterator find(
      const typename storeType::key_type &key)const{
    return _v.find(key);
  }
  size_t size()const{return _v.size();}
  bool hasEntry(const Tuple& t)const{
    size_t key = t.getKey();
    typename storeType::const_iterator itMap=_v.find(key);
    if(itMap==_v.end()){
      return false;
    }
    return itMap->second.find(t)!=itMap->second.end();
  }
  void delEntry(const Tuple& t){
    if(!hasEntry(t)){
      return;
    }
    typename Tuple::storeType::value_type key=t.getKey();
    typename storeType::mapped_type::iterator it=_v[key].find(t);
    if(_v[key].size()==1){
      _v.erase(_v.find(key));
    }else{
      _v[key].erase(it);
    }
  }
  std::set getTuples(const Tuple &t){
    std::set s;
    for(typename Tuple::const_iterator it=t.begin(); it!=t.end();
        ++it) {
      typename Tuple::const_iterator it2=it;
      ++it2;
      for(; it2!=t.end(); ++it2){
        typename Tuple::const_iterator it3=it2;
        ++it3;
        for(; it3!=t.end(); ++it3){
          Tuple generatedTuple(*it, *it2, *it3);
          s.insert(generatedTuple);
        }
      }
    }
    return s;
  }
  template
  void deleteTuples(const T& t){
    for(typename T::const_iterator it=t.begin(); it!=t.end();
         ++it){
      delEntry(*it);
    }
  }
  template
  bool hasAllTuples(const T& t)const{
    for(typename T::const_iterator it=t.begin(); it!=t.end();
         ++it){
      if(!hasEntry(*it)){
        return false;
      }
    }
    return true;
  }
  std::string toString()const{
    std::stringstream oss;
      for(typename storeType::const_iterator itMap=begin();
          itMap!=end(); ++itMap){
        ossfirstsecond.begin();
          it!=itMap->second.end();++it){
          osstoString()
bool checkList(const T& l){
  bool ok=true;
  for(typename T::const_iterator it=l.begin(); it!=l.end(); ++it){
    typename T::const_iterator it2=it;
    ++it2;
    for(;it2!=l.end();++it2){
     
      if(it->intersect(*it2).size()>2){
        std::couttoString()toString()
#include "useful.hpp"
#include
#include
#include
#include
#include
#include
template
std::set getList(const Tuple&t, const mymap &m){
  std::set s;
  for(typename Tuple::const_iterator it=t.begin(); it!=t.end();
      ++it){
    typename mymap::const_iterator itMap = m.find(*it);
    if(itMap!=m.end()){
      s.insert(itMap->second.begin(), itMap->second.end());
    }
  }
  typename std::set::const_iterator it=s.find(t);
  s.erase(it);
  return s;
}
template
bool tryAdd(const Tuple& t, storeTuple& m, U& outList){
  const typename storeTuple::mapped_type &s=m.getTuples(t);
  if(m.hasAllTuples(s)){
    m.deleteTuples(s);
    outList.insert(t);
    return true;
  }
  return false;
}
void getSolution(){

  MyMap ol;
  combinatorial(ol, 3,18);
  typedef std::set store;
  typedef MyMap::mapped_type::value_type Tuple;
  typedef std::set storeTuple;

  storeTuple outList;
  while(ol.size()){
    Tuple t3 = *(ol.front().begin());
    const std::set& s = getList(t3, ol);
    for(storeTuple::const_iterator it=s.begin(); it!=s.end(); ++it){
      const Tuple &nt = *it;
      Tuple t4 = t3 + nt;
      if (t4.size() == 5){
        if(tryAdd(t4, ol, outList)){
          break;
        }
      }
      storeTuple::const_iterator it2=it;
      ++it2;
      bool addedTuple = false;
      for(; it2!=s.end(); ++it2){
        const Tuple& thirdTuple = *it2;
        Tuple t5 = t4 + thirdTuple;
        if(t5.size()==5){
          if(tryAdd(t5, ol, outList)){
            addedTuple = true;
            break;
          }
        }
        if(t5.size()==6){
          Tuple test=t3+thirdTuple;
          if(test.size()==5 && tryAdd(t3+thirdTuple, ol, outList)){
            addedTuple = true;
            break;
          }
        }
        //if t5==4 e.g (1,3,4)(1,3,5)(3,4,5) next can be (4,5,6)
        //but shit
      }
      if(addedTuple){
        break;
      }
    }
    ol.delEntry(t3);
  }
 
  std::cout tuples;
 
  std::string str;
  while(std::getline(in, str)){
     std::istringstream iss(str);
     if(str.size()>5){
        size_t a,b,c,d,e;
        char junk;
        iss >> a;iss>>junk;
        iss >> b;iss>>junk;
        iss >> c;iss>>junk;
        iss >> d;iss>>junk;
        iss >> e;
        Tuple t(a,b,c,d,e);
        tuples.push_back(t);
    }
  }
  if(checkList(tuples)){
    std::cout<<"ok file"<<std::endl;
  }
}
int main(){
  getSolution();
  //checkList(std::string("data_5_18.txt"));
  return 0;
}


j'ai quand même pris soin de vérifier la liste fournie par Bramant52 qui est effectivement correcte :++:

comment je procède:
je génère toutes les combi de 3 elem dans une liste (des 3-tuples)
Je prends le premier tuple de la liste.
J'essaie de générer une permute de 5 en joignant des tuples de la liste
Si tous les tuples engendrés par la permute sont présents dans la liste
je les supprime tous de la liste
je supprime le tuple et passe au suivant

la grosse idée c'est qu'un tuple est compris que dans un seul block.
Un point intéressant, est qu'à la fin de mon algo, la liste est vide (bien que l'algo n'ait pas engendré un maximum de blocks)

Je pense qu`il y a un pont a etablir entre la combinatoire et l`algebre lineaire

c'est sur. Je suis tombé sur les t-design, en particulier les Steiner(3,5,15) qui veut dire qu'on cherche des blocks de 5 parmis 15 elements, tq si on prend 3 elements qq, ils n'apparaissent que dans un seul block. Mais ya une condition de plus... qui fait que ca donne pas le best. Mais assurément, ya des idées à récupérer.. sur les travaux qui ont été faits.

Si ce probleme m`interesse c`est pour solutionner un autre probleme plus fascinant.

bah tu peux dire que c'est pour ton loto lol

PS: j'en ai rien à cirer de l'optimum, plus intéressant est l'algo qui y mène ;)
la vie est une fête :)

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

par Bramant52 » 29 Aoû 2014, 20:59

Salut,

Le systeme Steiner que je connais n`a pas beaucoup a voir avec ce que je cherche.

http://www.ccrwest.org/cover/steiner.html

Le loto m`interesse c`est evident sauf que ce que je cherche n`a rien a voir avec le loto.
Je te le dirai un jour quand j`aurai fini.

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

par Bramant52 » 29 Aoû 2014, 21:03

Faut retourner a l`extraction de la sous matrice mais avec une autre matrice differente de celle proposee plus haut pour trouver a coup sur l`optimum.
Un probleme de transformation d`abord puis ensuite une technique "geometrique" pour extraire la sous matrice.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 30 Aoû 2014, 11:48

Je donne ici l'équation théorique à laquelle je suis arrivé:
q=(n-2)(n-3)(n-4)/(6(10-60/n+60/n(n-1))

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

par Bramant52 » 30 Aoû 2014, 17:08

nodjim a écrit:Je donne ici l'équation théorique à laquelle je suis arrivé:
q=(n-2)(n-3)(n-4)/(6(10-60/n+60/n(n-1))


Salut,

Est-ce possible d`avoir les valeurs de q pour n variant de 10 a 20 juste pour savoir en quoi ta formule differe de celle que j`ai deja donne en parlant de barriere evidente : C(n,3)/C(5,3) ou si tu preferes C(n,3)/10 ?

Merci.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 30 Aoû 2014, 20:05

n q
10 12
11 16,5
12 22
13 28,6
14 36,4
15 45,5
16 56
17 68
18 81,6
19 96,9
20 114
21 133
22 154
23 177,1
24 202,4
25 230
26 260
27 292,5
28 327,6
29 365,4
30 406
31 449,5
32 496

ça ne doit pas être très différent de C(n,3)/10....

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

par Bramant52 » 30 Aoû 2014, 20:20

nodjim a écrit:n q
10 12
11 16,5
12 22
13 28,6
14 36,4
15 45,5
16 56
17 68
18 81,6
19 96,9
20 114
21 133
22 154
23 177,1
24 202,4
25 230
26 260
27 292,5
28 327,6
29 365,4
30 406
31 449,5
32 496

ça ne doit pas être très différent de C(n,3)/10....


C`est egal a C(n,3)/10
Bref, cela reste complique d`obtenir par une formule simple l`optimum.
Pas impossible puisque j`ai trouve un principe de solution en retravaillant sur les triplets non couverts.
En theorie l`optimum est egal a C(n,3)/10 - R
ou R est le denombrement des triplets non couverts.
A quoi R est egal? That`s the question! De quoi R depend-il?
R depend a mon avis du nombre maximal de couples que l`on peut couvrir plusieurs fois sans creer une seule repetion de triplets.
Ce nombre depend de la taille de n.
Avec n=10, les couples sont repetes 1.3333 fois.
6 combinaisons de 5 = 60 couples or C(10,2)=45 donc 60/45=1.3333...
Plus la taille de n est elevee plus ce ratio croit.
n=18
ratio = 4.44444
etc....

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

par Bramant52 » 30 Aoû 2014, 20:37

En termes plus simples :

L`optimum O est egal a (C(n,2)*r)/10
ou r est ce fameux ratio.
Il y a un lien je pense avec les systemes Steiner.

n=10 les 10 nombres sont utilises exactement 3 fois chacun.
Donc (10,5) serait un groupe parfait.
S(2,3,7) fait partie du systeme Steiner
Il y a une peut-etre conjecture a deriver du systeme Steiner.
n=12, ou 16 ou 18 ou 22 etc... seraient-ils parfaits?

(Edit: j`ai corrige car j`ai oublie de diviser par 10)

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

par fatal_error » 30 Aoû 2014, 23:32

ce problème est en anglais appelé (au moins) sharing family set.
Il y a ce papier qui montre un algo (à coup de théorême des restes chinois) que j'ai pas encore regardé.

Les mots clés "intersecting sets" donnent également des résultats mais généralement avec une intersection de cardinal minimal ou fixé (mais pas inférieur ou égal).

Sinon, les mots clés associés sont extremal combinatorics qui est l'étude des lower upper bound, et je suis d'ailleurs tombé sur les fesses quand j'ai vu la multitude de papiers sur la combinatoire (voir http://www.combinatorics.org/ojs/index.php/eljc/search )
la vie est une fête :)

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

par Bramant52 » 30 Aoû 2014, 23:56

fatal_error a écrit:ce problème est en anglais appelé (au moins) sharing family set.
Il y a ce papier qui montre un algo (à coup de théorême des restes chinois) que j'ai pas encore regardé.

Les mots clés "intersecting sets" donnent également des résultats mais généralement avec une intersection de cardinal minimal ou fixé (mais pas inférieur ou égal).

Sinon, les mots clés associés sont extremal combinatorics qui est l'étude des lower upper bound, et je suis d'ailleurs tombé sur les fesses quand j'ai vu la multitude de papiers sur la combinatoire (voir http://www.combinatorics.org/ojs/index.php/eljc/search )


Merci pour le papier, je vais essayer de le lire si pas trop technique.
Quant a combinatorics.org je connais (trop pointus leurs recherches) et il y en a d`autres.

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

par Bramant52 » 31 Aoû 2014, 00:05

Cela dit, il y a un algorithme naif qui peut donner de bons resultats si on laisse le programme tourner longtemps.
1. On genere tous les quintuplets, on tire un au hasard.
2.On le compare 2 a 2 avec les autres restants.
3.On elimine les 3 et 4 en commun de la liste.
4. On a une nouvelle liste
Et on reboucle a partir de la nouvelle liste jusqu`a ce que la liste se vide.
On obtient une liste de combinaisons que l`on conserve.
On refait les memes etapes en redemarrant a 1.
On obtient une seconde liste que l`on compare a la precedente, si elle a plus de combinaisons que la premiere on la garde et on supprime la premiere sinon on la supprime tout en gardant la precedente.
On laisse tourner 2 jours jusqu`a obtenir la meilleure.
Aleatoire certes mais cela peut se rapprocher de l`optimum.

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

par Bramant52 » 31 Aoû 2014, 00:28

L`avantage de cet algorithme naif est que le stockage maximal de la matrice se reduit a 5*C(n,5) + 5*M (M etant la matrice optimale)
La probabilite de trouver la matrice optimale est grande.
Pour n=10 la matrice optimale est de 5*6=30 sauf qu`il y a 42 matrices 5*6 remplissant les memes conditions.

Si le programme tombe sur une serie de valeurs identiques maximales en forte proportion il s`arrete et affiche l`un des sous ensembles ayant la plus haute valeur. En principe, cela serait proche de l`optimum voire l`optimum meme.

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

par Bramant52 » 31 Aoû 2014, 00:33

Voila une liste des principales revues de Combinatoire classees selon un score rating.
Elle inclut un grand nombre de pays.

http://www.scimagojr.com/journalrank.php?category=2607

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

par fatal_error » 31 Aoû 2014, 01:39

Aleatoire certes mais cela peut se rapprocher de l`optimum.

beurk
j'ai quand même implem l'algo dans la journée (pas précisé parce que pas super), mais les résultats sont pas super, c'est rapide (enfin relativement) mais par exemple pour 15 j'ai que 26 solutions et pour 18 toujours 51.
L'heuristique est de choisir le 3tuple tq le nombre de combinaisons qu'il génère et qui sont disponibles est minimal. Mais ca change pas grand chose...

J'ai implem viteuf l'algo de Blocki, qui est très bien décrit et ya quand même des restrictions fortent sur le n. Il doit etre décomposable en somme de 5 termes co premiers et donc pour nos ptites valeurs c'est pas la gloire.
par exemple sauf erreur, le plus petit n est 2,3,5,7,11 de somme 27 et le groupe max engendré par l'algo est 2*3*5==30 or, c'est sur que ya des groupes plus gros

reste à checker les ref
la vie est une fête :)

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

par Bramant52 » 31 Aoû 2014, 14:01

Le tri croise reste la meilleure solution sauf que cela me met la memoire out.
Mais il y a une autre solution basee sur les triplets.
Je suis en train de la clarifier car c`est encore confus dans ma tete.
Je laisse decanter 2 ou 3 jours, je travaille sur 3 nouveaux jeux en parallele.
A bientot.

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

par Bramant52 » 31 Aoû 2014, 22:53

J`ai trouve une formule donnant une borne plus precise a plus ou moins un pres :

Optimum <= (C(n,3)-6*n)/C(5,3)

n=18 O=70
n=15 O=36
n=10 O=6

il reste a expliquer le 6*n (pourquoi 6?)

Edit : j`ai encore oublie de diviser par C(5,3)=10.

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

par Bramant52 » 01 Sep 2014, 17:20

Je pense que l`on peut obtenir une formule exacte pour l`optimum.
Cela passe par une equation diophantienne avec contraintes. La difficulte est de cerner ses contraintes. Je les comprends mais n`arrive toujours pas a trouver le comment.
L`optimum est atteint quand on a des triplets que l`on ne peut regrouper en combinaisons de 4 et que l`on a des quadruplets impossibles a regrouper en groupes de 5.
Les quintuplets restants sont optimaux.
Pour n=10 j`obtiens
- 40 triplets impossibles a regouper en 4
- 5 quadruplets impossibles a
et 6 quintuplets optimaux.

La formule generale est :

10*x+4*y+z=C(n,3)

x = l`optimum recherche
y = le nombre de combinaisons de 4 impossible a regrouper en 5
z = les triplets impossibles a regrouper en 4 ou en 5.
n=10
10*6+4*5+40=120

Ma conjecture est que x,y,z sont lies.
Comment? Je ne sais pas pour l`instant.
Si on trouve le lien on pourrait exprimer l`optimum de maniere directe.
Mes neurones sont trop vieux alors si quelqu`un peut se pencher sur ce probleme, la solution serait utile. Ce serait peut-etre un bon resultat a publier en plus sophistique (Latex etc...).

Si l`on a une formule exacte, il serait, a mon avis, plus facile de generer cet ensemble optimal de combinaisons sans recourir au tri croise

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

par Bramant52 » 02 Sep 2014, 22:27

La formule generale est :

10*x+4*y+z=C(n,3)

x = l`optimum recherche
y = le nombre de combinaisons de 4 impossible a regrouper en 5
z = les triplets impossibles a regrouper en 4 ou en 5.
n=10
10*6+4*5+40=120

Je viens de trouver une borne a z
z>=C(n,3)/10

Avec cela on peut reduire le nombre de solutions (x,y,z).
Connaissant la borne inferieure de z, on peut reduire le champ de valeurs solutions de x et de y.
x pourrait etre exprime en fonction de y sous forme d`inequation

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 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