Combinatoire

[nodjim]

Oui Nicolas L, tu as bien résumé ce que Groucho et moi avons écrit. Je ne suis cependant pas en mesure de suivre ce qu'a écrit Groucho.

[Bramant52]

Merci pour toutes ces contributions.
Tri croise (et non tir croise) est documente sur Internet sauf que ce n`est pas exactement ce que je veux.
C`est un tri simultane que j`utilise.
Quand on change l`ordre en lignes on le change simultanement en colonnes
La matrice est symetrique.
A l`interieur je ne mets que des valeurs 0 et 1 pour simplifier.
Exemple simple :
1 2 3
1 1 1 0
2 1 0 1
3 0 1 1

On change notre tri : au lieu de 1,2,3 on classe 1,3,2
1 3 2
1 1 0 1
3 0 1 1
2 1 1 0

Cela dit, j`ai trouve la solution (impossible peut-etre a programmer, je dis bien peut-etre) et je la realiserai sur ecran avec (3003*3003) a mon retour. Je pars pour quelques jours en vacances hors de Toronto a partir de demain.

Merci cependant a tous.

[Bramant52]

Desole pour les colonnes de la matrice il y a un espace apres 1 2 3 et 1 3 2

[Groucho]

Oui Nicolas L, tu as bien résumé ce que Groucho et moi avons écrit. Je ne suis cependant pas en mesure de suivre ce qu'a écrit Groucho.

En fait, on peut arriver à 130. Ce que j'écris n'est pas compliqué. J'expliquede façon naive.

On numérote les boule de 0 à 24. A la boule , numéro n on fait correspondre deux entiers x_n et y_n déterminés par :
avec et
( est le quotient entier de n par 5 et le reste )

Maintenant, si a, b et c sont trois nombres compris entre 0 et 5 (0 compris, 5 non compris), on considère l'ensemble de boules telles . D'une part, a, b et c étant fixés, en faisant varier x_n de 0 à 5, on obtient un ensemble de 5 boules . D'autre part, on vérifie facilement que étant donné les ensembles et n'ont pas plus de 2 points en commun.

Je dis qu'on peut aller jusqu'à 130 parce qu'on peut ajouter pour chaque a compris entre 0 et 5, l'ensemble des 5 boules où .

[Bramant52]

Pour (25,5) le maximum devrait se situer aux alentours de 200. J`utilise une formule simple pour y arriver.
Je vous donne le maximum pour (18,5) il est de 71 en theorie, j`ai reussi 66.
A Groucho, peux-tu donner ton maximum theorique pour 18 boules?
Je peux vous envoyer mes 69 combinaisons s`agissant de 18 si vous voulez.

Merci.

[Bramant52]

Un detail cependant : avoir au plus 2 en commun peut etre atteint avec beaucoup moins de combinaisons. Ce que l`on cherche c`est un maximum possible.

[Bramant52]

Je resume mon probleme.
On part d`une matrice symetrique C(n,5)*C(n,5).
On la remplit de 0 et de 1.
On note 0 si les combinaisons (ligne,colonne) ont 4 ou 3 en commun et 1 si elles ont 5,2,1,0.
Une combinaison a toujours 5 en commun avec elle-meme.
Donc, la diagonale (gauche, droite) ne comprendra que des 5 (en termes binaires des 1).
Pour trouver la solution, il s`agira d`extraire la plus grande matrice carree ne contenant que des 1.
Le meilleur moyen pour y arriver est le tri croise (voir explication plus haut).
Une fois obtenu un maximum "local" on peut verifier s`il est optimal par permutation.
6 est le maximum local pour C(10,5). Si on arrive a retrouver par permutation 42 autres solutions de 6 on sera sur que le nombre 6 est optimal. Cette etape est bien plus complexe quand n devient grand.

[Bramant52]

Pour (18,5) voila mes 66 combinaisons :

1,2,3,7,9
1,2,4,10,12
1,2,5,11,16
1,2,8,14,15
1,2,13,17,18
1,3,4,6,16
1,3,5,10,15
1,3,8,11,13
1,3,12,14,18
1,4,5,8,17
1,4,7,11,14
1,4,9,13,15
1,5,6,9,14
1,5,7,12,13
1,6,7,8,10
1,6,11,12,15
1,7,15,16,18
1,8,9,12,16
1,9,10,11,18
1,10,13,14,16
2,3,4,5,13
2,3,6,11,14
2,3,8,10,17
2,3,12,15,16
2,4,6,7,18
2,4,8,9,11
2,4,14,16,17
2,5,6,8,12
2,5,7,10,14
2,5,9,15,17
2,6,9,10,16
2,7,8,13,16
2,7,11,12,17
2,9,12,13,14
2,10,11,13,15
3,4,7,8,12
3,4,9,10,14
3,4,11,15,17
3,5,6,7,17
3,5,8,14,16
3,5,9,11,12
3,6,8,9,15
3,6,10,12,13
3,7,10,11,16
3,7,13,14,15
3,9,13,16,18
4,5,6,10,11
4,5,7,9,16
4,5,12,14,15
4,6,9,12,17
4,7,10,13,17
4,8,10,15,16
4,11,12,13,16
5,6,13,15,16
5,7,8,11,15
5,8,9,10,13
5,10,12,16,17
5,11,13,14,17
6,7,9,11,13
6,7,12,14,16
6,8,11,16,17
6,10,14,15,17
7,8,9,14,17
7,9,10,12,15
8,10,11,12,14
8,12,13,15,17

Je pense que l`on peut faire mieux

[fatal_error]

toujours dans mon trip, mais avec un algorithme
un peu mieux que le simplexeà mon avis:
en considérant la matrice des a_ij, on crée une nouvelle matrice qui vaut 1 si a_ij bestGroup.length
bestGroup=g.indexes
endfi
endfor
[/CODE]

[Bramant52]

Pour (15,5) la matrice est de 3003*3003 (C(15,5)=3003).
Je viens de trouver une piste pour extraire la plus grande sous-matrice carree ne contenant que des 1. Autrement dit la sous-matrice solution.

Allez! a bientot je quitte les vacances et leurs preparatifs m`attendent.

[Groucho]

Ca devient compliqué, et je crains ne pas avoir beaucoup de temps dans les semaines qui viennent pour y réfléchir. Alors, je vous livre mes dernières cogitations.

En fait, l'idée que j'ai eu peut être bien simplifiée et un peu généralisée. Elle peut donner des résultats pour un nombre de boules égales à 5p, pour p = 3,4 ou 5.

L'idée (une fois simplifiée) est de placer les boules sur une grille à 5 colonnes et p lignes. On commence par trouver des combinaisons qui contiennent un élément et un seul sur dans chaque colonne. Pour cela, on choisit les 3 premiers indépendamment (soit p^3 possibilités), et pour chacune de ces possibilités, on la complète de façon à satisfaire la condition voulue. C'est facile à l'aide d'un peu d'algèbre linéaire (par exemple, si a, b et c (compris entre 0 et p-1) sont les positions des trois premières boules dans les colonnes 1, 2, 3, on place la quatrième en position a+b+c (calculé dans Z/pZ) et la cinquième en a+b-c. Cela peut se générer facilement à l'aide d'un tableur.
On obtient déjà p^3 combinaisons, mais on peut ajouter des combinaisons, qui doivent cependant se tenir sur 2 colonnes au plus.
Il n'y a aucun problème pour en ajouter 5. Ce qui fait respectivement 32, 69 et 130 combinaisons. Je pense que pour p=5, on doit pouvoir ajouter 20 combinaisons, (soit 145, à confirmer).

Les ensembles de combinaisons qu'on obtient sont maximaux (ce qui veut dire qu'on ne peut rien y ajouter), mais ça ne veut pas dire qu'on ne peut pas obtenir un autre ensemble plus important

[fatal_error]

hello,

qq résultats:
pour 5 parmi 10, je trouve également 6 combi:

Code: Tout sélectionner

found better solution : 6
1111100000
1100011100
0011011010
0010110101
1000101011
0101000111


pour 5 parmi 15, mon algo termine pas mais trouve très vite une solution de 29 mains:

Code: Tout sélectionner

found better solution : 29
111110000000000
110001110000000
001101101000000
001011010100000
100010101100000
010100011100000
000110110010000
010011001010000
101000011010000
100101000110000
011000100110000
101001000001100
010100100001100
000010011001100
000111000001010
011000010001010
100000100011010
001010100000110
100100010000110
010001000100110
100100001001001
000001100101001
001010000011001
011000001000101
000110000100101
000001010010101
000000111000011
101000000100011
010100000010011


et attention, l'implem mega moche :ptdr:

Code: Tout sélectionner

#include
#include
#include
#include
#include
#include
#include
template
class Combination{
public:
  std::string toString() const{
    return _v.to_string();
  }
  std::string toHumanString() const{
    std::stringstream oss;
    for(size_t i=0; i& other)const{
    const typename Combination::bitVect &v=_v & other._v;
    return v.count();
  }
  bool operator[](size_t pos)const{
    return _v[pos];
  }
  typename std::bitset::reference operator[](size_t pos){
    return _v[pos];
  }
  typedef std::bitset bitVect;
  static const size_t size=T;
  bitVect _v;
};
template
void combinatorial(std::deque >& ol, size_t k){
  std::vector v(n);
  std::fill(v.begin() + n - k, v.end(), true);
  do {
      Combination combination;
      for (size_t i = 0; i
std::string toString(const std::deque >& ol){
  std::string s;
  for(typename std::deque >::const_iterator it=ol.begin();
    it!=ol.end(); ++it){
    s+=it->toString()+"\n";
  }
  return s;
}
template
class Combi{
public:
  static const int value=(Combi::value*n)/k;
};
template
class Combi{
public:
  static const int value=n;
};
template
class Matrix{
public:
  Matrix():_v(n){};
  Combination& operator[](size_t pos){
    return _v[pos];
  }
  std::string toString()const{
    std::string s;
    for(size_t i=0;i > _v;
  typedef Combination rowType;
};
template
void fill(Mat& m, const List &l){
  for(size_t i=0;i
class SolutionDisplayer{
public:
  SolutionDisplayer(T* aList):_list(aList){};
  std::string toString(const std::set &solIndexes)const{
    std::string s;
   
    for(std::set::const_iterator it=solIndexes.begin(); it!=solIndexes.end();++it){
      std::cout
class SolutionFinder{
public:
  SolutionFinder(Mat* mat, Displayer s):_matrix(mat),_bestCount(0),_solutionDisplayer(s){}
  class Solution{
  public:
    std::set _indexes;
    std::bitset _intersect;
    typedef std::set SolutionIndexes;
  };
  void explore(Solution s, size_t k){
    Solution g;
    g = s;
     g._indexes.insert(k);
     g._intersect = s._intersect & (*_matrix)[k]._v;
     if(g._indexes.size() > _bestCount){
       _bestCount = g._indexes.size();
       _bestSolution = g;
       std::cout find(){
    Solution s;
    s._indexes.insert(0);
    s._intersect = (*_matrix)[0]._v;
    for(size_t i=1;i
void compute(){
  std::deque > aList;
  combinatorial(aList, k);
  Matrix::value> adjencyMatrix;
  fill(adjencyMatrix, aList);
  SolutionDisplayer > > solutionDisplayer(&aList);
  SolutionFinder::value>,
      SolutionDisplayer > >
  > solutionFinder(&adjencyMatrix, solutionDisplayer);
  solutionFinder.find();
}
int main() {
    compute();
    return 0;
}


j'intuite que 29 c'est le mieux, faut que je réfléchisse un peu..

[Groucho]

Bon, j'ai encore dit des bêtises, je vais trop vite.

Je retire donc ce que j'ai dit dans mon dernier message sur les cas 15 et 20. Pour 25, je confirme : au moins 130, certainement plus, peut être 145.

[fatal_error]

salut Groucho,

comme j'ai pas lu ton poste parce que c'était un peu compliqué et que je savais pas si ca aboutissait,
j'ai continué de mon côté pour élaguer l'arbre de recherche.
La seule conclusion à laquelle je suis parvenu, est lors de l'exploration d'une nouvelle ligne, de regarder si le set courant + la nouvelle ligne forme un graphe isomorphe à un graphe déjà exploré.

J'ai pas encore mis en place, mais même avec une procedure plus rapide et plus destructive pour la comparaison de graphe, l'algo ne converge pas...

est-ce que tu peux détailler les solutions pour ton p qui marche, histoire de voir si ca tient!

---mis à part
une deuxième possibilité c'est de chercher à partir de la matrice d'adjacence à opérer des isomorphismes jusqu'à ce qu'on obtienne une matrice carrée de 1 dans un coin. (la plus grande possible). Mais bon, de là à trouver une telle suite...

[Groucho]

salut Groucho,

comme j'ai pas lu ton poste parce que c'était un peu compliqué et que je savais pas si ca aboutissait,
j'ai continué de mon côté pour élaguer l'arbre de recherche.
La seule conclusion à laquelle je suis parvenu, est lors de l'exploration d'une nouvelle ligne, de regarder si le set courant + la nouvelle ligne forme un graphe isomorphe à un graphe déjà exploré.

J'ai pas encore mis en place, mais même avec une procedure plus rapide et plus destructive pour la comparaison de graphe, l'algo ne converge pas...

est-ce que tu peux détailler les solutions pour ton p qui marche, histoire de voir si ca tient!

---mis à part
une deuxième possibilité c'est de chercher à partir de la matrice d'adjacence à opérer des isomorphismes jusqu'à ce qu'on obtienne une matrice carrée de 1 dans un coin. (la plus grande possible). Mais bon, de là à trouver une telle suite...

Bon, le seul cas où ça marche vraiment (du moins pour l'instant), c'est pour 25 boules. 2 étapes: on en trouve d'abord (facilement) 125 combinaisons, auxquelles on peut ajouter au moins 5 combinaisons, et certainement plus. J'explicite:

Les 125 combinaisons peuvent être générées très facilement à l'aide d'un tableur (excel par exemple.
On place les boules sur une grille 5x5, autrement dit chaque boule sera repérée par un couple (x,y), avec x et y compris entre 0 et 4. Pour a, b et c compris entre 0 et 4, définit l'ensemble de boules C(a,b,c)={(0,a),(1b),(2,c),(3,a+b+c), (4,a+2b,+3c)} calculé modulo 5, ce qui veut dire que a+b+c, s'il est supérieur à 5 doit être remplacé par le reste de sa division par 5. Itou pour a+2b+3c.
Voilà, on a nos 125 combinaisons, car on peut vérifier, soit avec un peu d'algèbre linéaire, soit à la main, que 2 telles combinaisons ne peuvent pas se couper en plus de 2 boules.

Maintenant, on peut impunément ajouter des combinaisons qui sont incluses sur une ou 2 colonnes (puisque les 125 précédentes ne contiennent qu'un point sur chaque colonne).

première possibilité paresseuse : on ajoute les combinaisons correspondantes aux 5 boules sur une même colonne : ca nous amène à 130

deuxième possibilité: on ajoute des combinaisons tenant sur 2 colonnes, 3 boules sur l'une, 2 sur l'autre. Le jeu est d'en ajouter le maximum en respectant la règle, étant entendu qu'on n'a pas à se soucier des 125 premières. J'ai l'impression qu'on peut arriver jusqu'à 20, mais comme j'ai déjà dit beaucoup de bêtises, je n'en jurerais pas.

[fatal_error]

au risque de paraitre un peu teubé,
tu sembles prendre le produit 5*5*5 correspondant aux valeurs possibles de a,b et c.
Mais si tu prends a=b=c=0
et a=b=c=1, tu as deux combinaisons qui sont pas compatibles (trois boules commun) non?

je suppose que x c'est les lignes et y les colonnes.

note à part:
comment peut on montrer que pour a!=b!=c, a,b,c dans {0,4} que a+b+c %5 c'est différent de a et b et c?
edit: c'est pas le cas pour
a b c d e
0 1 4 0 0
0 2 3 0 0
1 2 3 1 1
d==a+b+c
e==a+2b+3c

edit2: bon hier j'étai torché, ca marche bien on a pas deux combi non compatibles. mais je sais pas pourquoi :(

edit3: si c'est bon
pour a,b,c différent, au max d==d' et e==e'
donc au mieux a==b (ou b==c ou c==a) et c différents
soit C'(a,b,c')
on a d=a+b+c%5, d'=d%5 (-c+c')%5 donc d'!=d
de même e'=e + 3(c-c') %5 donc e'!=e

[fatal_error]

de mon côté avec une autre approche... cette fois plus couteuse en mémoire (à priori...)

une autre manière d'explorer c'est de considérer la matrice de même taille, mais avec pour élément x:
x={e_i} ou e_i est un ensemble qui contient les index d'un bloc.
Un bloc désigne les combinaisons telles quelles sont toutes compatibles.
Bref e_i contient l'index de ces combinaisons.

Code: Tout sélectionner

soit y={e_j}
x*y=
  pour i des e_i de x
   pour j des e_j de y
    si compatible(e_i,e_j)
     ajouter {e_iUe_j}
  //si rien ajouté, ensemble vide==0

proc compatible(e_i,e_j)
  pour tout index k de e_j
    si(k in e_i)
      return false;
    finsi
    si exist combi de e_i tq combi(k) pas compatible
      return false;
    finsi
  finpour
  return true
finproc

x+y={x,y} (un vecteur dont les elem sont soit e_i soit e_j)

bref on note M une telle matrice et comme on sait qu'on a a peu pres 30 combinaisons, ben
M
M^2
M^4
M^8
M^16
M^24 (16+8)
...etc

avec l'idée qu'à la fin, le calcul du produit est plus rapide parce que plein de 0 (on est pas censé avoir la masse es blocks de taille 25 mais plutot plein de 0)

l'initialisation de M est faite en considérant tous les blocks de taille 2
donc M_11==0
(donc comme notre matrice des posts d'avant mais avec des zeros sur la diagonale)
avec un peu de chance, M^2 contient alors des ensembles de blocks de taille 3 et ainsi de suite.

reste à coder... mais ca donne au moins du 30*N^2 avec l'opération * qui prend du temps et l'opération + qui fait péter la mémoire XD

[Groucho]

au risque de paraitre un peu teubé,
tu sembles prendre le produit 5*5*5 correspondant aux valeurs possibles de a,b et c.
Mais si tu prends a=b=c=0
et a=b=c=1, tu as deux combinaisons qui sont pas compatibles (trois boules commun) non?

je suppose que x c'est les lignes et y les colonnes.

note à part:
comment peut on montrer que pour a!=b!=c, a,b,c dans {0,4} que a+b+c %5 c'est différent de a et b et c?
edit: c'est pas le cas pour
a b c d e
0 1 4 0 0
0 2 3 0 0
1 2 3 1 1
d==a+b+c
e==a+2b+3c

Pas de panique.

On a
0 1 4 0 4 (et non pas 0 1 4 0, 0)
0+1+4 = 5=0 et 0 +2+12=14=4
et 0 2 3 0 3
0+2+3=5=0 et 0+4+9=13=3

Ca colle


Pour montrer d'une façon générale que ça marche, il faut montrer que pour tout a,b,c compris entre 0 et 4, étant donné 3 éléments parmi les 5 suivants

a , b , c, a+b+c, a+2b+3c


on peut retrouver les 2 autres. Par exemple, à partir de a+b+c et a+2b+3c et a

on peut retrouver, par soustraction b+c et 2b+3c, puis c, puis b. Donc s'il y en a 3 égaux, les 5 sont égaux
C'est là où un peu d'algèbre linéaire est utile.


avec a=b=c=0, on obtient 0,0,0,0,0, c'est à dire les boules (0,0),(1,0),(2,0)(3,0)(4,0), autrement dit la boule se trouvant en bas de la première colonne, en bas de la seconde colonne etc.

Il n'y a aucune boule en commun avec ce que l'on obtient avec a=b=c=1 ( 1,1,1,3,1).


Je pense que ce défi est intéressant car il montre comment un peu de maths (nous sommes sur un forum de math) un peu théorique peut aider à résoudre des problèmes purement combinatoires. En particulier, pour le cas 20 boules, la même méthode permet de trouver 69 combinaisons (64 plus 5). L'intuition est la même, mais cette fois, il faut faire les calculs dans le corps F_4 à 4 éléments (en non pas dans Z/4Z, ça devient plus trapu)

[Bramant52]

Salut Groucho,

Tu trouves quel maximum pour (18,5)?
Moi je trouve 66 combinaisons, je les ai postees.
Apres avoir fait des tests, je pense, comme dit precedemment, avoir trouve le principe de solution : le tri croise.
La je poste les maximums (a plus ou moins un pres) pour tout n=10 jusqu`a 30.
n max(+ou-1)
10 6
11 10
12 14
13 19
14 26
15 34
16 43
17 53
18 65
19 78
20 94
21 111
22 129
23 150
24 173
25 199
26 225
27 256
28 288
29 323
30 361

L`approximation a plus ou moins un pres depend de la divisibilite par 5.
J`essaie d`ameliorer ma formule.
Pour 18 j`avais trouve 66 et ma formule me donne 65.
Pour n=25 il faut compter un maximum de 199 voire 200 et non 135.
A plus tard

[Bramant52]

Je suis arrive a extraire de la matrice principale (symetrique et carree) composee de 0 et de 1 une sous-matrice (symetrique et carree) ne contenant que des 1.
L`algorithme est rapide et peut etre ameliore.
Comme je travaille sur Excel avec 15 boules, mon ordi n`a pas suffisamment de memoire pour gerer cela. Il bloque carrement.
J`essaierai de solutionner cela autrement en travaillant sur une matrice reduite et je vous enverrai le resultat maximal pour (15,5).