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
