Combinatoire

Olympiades mathématiques, énigmes et défis
Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 20 Aoû 2015, 21:06

Enfin!
Je pense avoir trouve une solution elegante et definitive a ce probleme.
Il etait temps autrement mon esprit n`aurait pas fini d`etre tourmente.



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

par Mario2015 » 20 Aoû 2015, 23:05

Je retire ce que j`ai dit precedemment.
J`ai commis une erreur donc toujours pas de solution.
Retour au cottage! grrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
Comment faire pour se debarasser d`un probleme qui vous obsede???????????
Meme quand je dors mon cerveau continue a travailler (pour des cacahuetes en fin de compte).

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

Re: Combinatoire

par fatal_error » 03 Juil 2019, 13:43

bj

quelques années plus tard (... :) )
pour le 3,5,18

451 blocks
Code: Tout sélectionner
3,6,13,14,16
7,10,12,14,16
1,3,10,15,16
2,5,6,14,16
1,5,8,14,16
3,8,12,13,16
1,3,4,14,16
4,5,11,14,16
0,6,11,14,16
8,10,11,14,16
2,9,11,14,16
3,5,9,14,16
1,2,5,7,17
9,13,14,15,16
1,4,7,9,17
3,5,8,9,17
2,4,5,8,17
0,1,2,8,17
5,6,7,8,17
2,8,11,15,16
3,7,12,15,16
6,8,12,15,16
5,7,10,15,16
4,8,10,15,16
2,9,10,15,16
5,6,11,15,16
1,4,11,15,16
10,11,13,15,16
4,7,14,15,16
0,3,14,15,16
1,2,14,15,16
0,2,13,15,16
4,9,12,15,16
5,8,13,15,16
4,6,13,15,16
4,5,6,10,16
3,6,8,10,16
4,6,7,9,16
2,3,4,10,16
1,2,5,10,16
0,2,7,11,16
5,7,8,11,16
0,4,9,10,16
0,2,3,6,16
0,2,4,5,16
11,12,13,14,15
5,7,13,14,15
1,4,13,14,15
0,1,5,9,16
1,2,3,9,16
1,4,5,7,16
1,3,6,7,16
0,3,4,7,16
3,4,5,8,16
0,1,3,8,16
0,5,6,7,16
1,2,8,13,16
2,7,9,13,16
0,3,9,13,16
6,7,8,13,16
0,1,4,13,16
2,10,11,12,16
2,3,5,13,16
6,9,11,13,16
1,7,12,13,16
2,6,10,13,16
4,8,9,13,16
5,9,10,13,16
2,4,11,13,16
0,5,11,13,16
0,8,10,13,16
4,7,10,13,16
2,4,6,12,16
1,5,6,12,16
0,8,9,11,16
3,7,9,11,16
8,9,10,12,16
0,6,10,12,16
3,5,10,12,16
6,7,11,12,16
3,4,11,12,16
0,1,11,12,16
2,5,9,12,16
2,7,8,12,16
1,4,10,12,16
3,6,9,12,16
3,5,13,15,17
0,1,13,15,17
2,9,13,15,17
0,2,12,15,17
1,8,12,15,17
4,7,12,15,17
5,12,14,15,17
6,13,14,15,17
1,9,14,15,17
2,8,14,15,17
0,7,14,15,17
1,12,13,14,17
1,2,11,15,17
3,8,10,15,17
5,8,11,15,17
4,9,11,15,17
3,6,11,15,17
0,5,9,15,17
4,5,10,15,17
1,7,10,15,17
5,7,14,16,17
11,12,13,16,17
2,10,14,16,17
6,9,14,16,17
8,9,15,16,17
11,14,15,16,17
7,13,15,16,17
10,12,15,16,17
0,13,14,16,17
4,12,14,16,17
0,6,15,16,17
1,5,15,16,17
2,4,15,16,17
4,5,9,16,17
7,8,10,16,17
0,5,10,16,17
2,3,7,16,17
0,1,7,16,17
3,5,6,16,17
1,4,6,16,17
0,2,9,16,17
2,6,8,16,17
0,4,8,16,17
5,8,12,16,17
1,3,13,16,17
7,9,12,16,17
2,5,11,16,17
3,9,10,16,17
4,10,11,16,17
1,2,12,16,17
0,3,12,16,17
1,9,11,16,17
3,8,11,16,17
3,6,8,12,17
4,6,9,12,17
0,1,9,12,17
0,9,10,11,17
1,3,7,12,17
0,5,6,12,17
1,4,5,12,17
2,3,5,12,17
2,7,11,12,17
5,10,11,12,17
0,8,11,12,17
6,7,10,12,17
2,8,10,12,17
4,8,9,10,17
2,5,9,10,17
0,2,4,10,17
0,1,3,10,17
0,7,8,9,17
3,5,7,10,17
1,5,6,10,17
3,4,6,10,17
2,6,10,11,17
2,8,9,11,17
0,1,5,11,17
2,3,4,11,17
1,6,8,11,17
0,6,7,11,17
4,5,7,11,17
2,7,9,14,17
0,4,11,14,17
4,7,10,14,17
0,3,9,14,17
1,7,8,14,17
4,6,8,14,17
6,11,12,14,17
9,10,12,14,17
1,10,11,14,17
5,9,11,14,17
1,4,10,13,17
3,7,9,13,17
6,8,10,13,17
2,7,10,13,17
4,6,7,13,17
2,3,8,13,17
1,5,8,13,17
0,5,7,13,17
0,6,9,13,17
0,10,12,13,17
5,9,12,13,17
2,3,6,14,17
0,1,6,14,17
1,3,5,14,17
0,2,5,14,17
1,2,4,14,17
3,10,11,13,17
4,8,11,13,17
1,7,11,13,17
5,6,11,13,17
7,8,12,13,17
2,6,12,13,17
3,4,12,13,17
1,2,4,9,13
2,5,7,8,13
0,3,6,7,13
3,4,5,7,13
4,5,6,8,13
0,3,5,8,13
3,5,6,10,13
3,4,8,10,13
1,6,8,9,13
5,6,7,9,13
0,2,5,10,13
0,3,5,11,12
1,2,6,11,12
2,3,8,11,12
0,2,4,11,12
0,1,5,6,13
1,2,3,7,13
0,2,4,7,13
1,3,4,6,13
1,5,9,11,12
4,6,8,11,12
4,7,9,11,12
4,10,11,12,13
5,8,11,12,13
3,7,11,12,13
0,7,9,12,13
2,3,9,12,13
1,6,10,12,13
0,4,7,8,14
0,3,5,6,14
0,1,4,5,14
2,3,5,7,14
1,4,6,7,14
3,8,9,11,13
0,4,9,11,13
0,1,3,11,13
2,8,9,10,13
1,7,9,10,13
4,6,9,10,13
2,3,6,11,13
1,4,5,11,13
0,4,6,12,13
1,4,8,12,13
1,2,10,11,13
1,3,5,12,13
2,4,5,12,13
0,1,2,12,13
7,8,10,11,13
2,3,5,8,10
4,6,7,8,10
0,5,7,8,10
1,3,5,7,11
0,3,7,9,10
4,5,7,9,10
1,3,6,9,10
1,3,4,7,8
2,3,4,6,8
1,2,6,7,8
0,1,2,4,6
2,4,5,6,7
0,4,6,8,9
0,2,5,8,9
3,6,7,8,9
1,3,4,5,10
1,2,5,6,9
0,3,4,5,9
2,3,4,7,9
0,3,4,8,12
0,6,7,8,12
1,5,7,8,12
3,4,5,6,12
0,1,3,6,12
2,3,6,7,12
0,2,5,7,12
0,1,4,7,12
0,4,5,10,12
0,2,3,10,12
3,4,7,10,12
0,1,8,10,12
1,2,7,10,12
2,5,6,10,12
0,2,6,9,12
2,4,8,9,12
5,6,8,9,12
1,3,8,9,12
1,6,7,9,12
3,5,7,9,12
4,5,6,9,11
0,3,6,9,11
2,6,7,9,11
0,5,7,9,11
3,5,6,8,11
1,2,5,8,11
0,1,4,8,11
0,1,2,9,11
1,3,4,9,11
2,4,7,8,11
0,3,7,8,11
2,4,9,10,11
4,5,8,10,11
1,3,8,10,11
6,8,9,10,11
1,2,3,4,12
3,5,9,10,11
0,3,4,10,11
1,7,8,9,11
2,5,7,10,11
3,6,7,10,11
0,2,8,10,11
0,1,7,10,11
0,5,6,10,11
1,4,6,10,11
4,7,10,11,15
0,1,5,12,15
1,3,11,12,15
4,5,11,12,15
8,10,11,12,15
2,9,11,12,15
0,8,9,12,15
3,9,10,12,15
0,7,10,12,15
4,6,10,12,15
2,6,8,10,15
6,7,9,10,15
5,8,9,10,15
0,1,2,10,15
0,3,6,10,15
6,7,8,11,15
2,3,10,11,15
1,5,10,11,15
0,4,6,11,15
0,2,5,11,15
6,8,9,14,15
4,5,6,14,15
2,3,12,14,15
3,8,11,14,15
7,9,11,14,15
1,7,12,14,15
4,8,12,14,15
0,6,12,14,15
1,6,10,14,15
2,5,10,14,15
3,4,10,14,15
2,4,11,14,15
0,1,11,14,15
3,7,10,13,15
2,4,10,13,15
7,8,9,13,15
2,5,6,13,15
0,4,5,13,15
3,6,8,13,15
0,3,12,13,15
5,10,12,13,15
1,9,12,13,15
2,8,12,13,15
6,7,12,13,15
3,4,11,13,15
0,9,10,13,15
1,8,10,13,15
5,9,11,13,15
0,8,11,13,15
2,7,11,13,15
1,6,11,13,15
2,6,8,11,14
4,8,9,11,14
2,4,10,12,14
1,5,10,12,14
3,6,10,12,14
0,2,8,12,14
3,5,8,12,14
4,5,7,12,14
0,3,7,12,14
0,4,9,12,14
1,2,9,12,14
1,6,8,12,14
1,3,7,10,14
0,2,7,10,14
0,4,6,10,14
3,4,6,9,14
2,4,5,9,14
2,3,8,9,14
0,1,8,9,14
0,6,7,9,14
1,5,7,9,14
1,3,6,11,14
5,6,7,11,14
0,5,8,11,14
3,4,7,11,14
1,2,7,11,14
5,6,8,10,14
0,3,8,10,14
1,2,8,10,14
7,8,9,10,14
0,2,3,11,14
2,6,9,10,14
0,5,9,10,14
1,4,9,10,14
2,3,4,5,15
1,2,3,6,15
0,1,3,4,15
0,3,5,7,15
0,2,6,7,15
1,2,4,7,15
2,7,12,13,14
0,5,12,13,14
9,10,11,13,14
8,10,12,13,14
6,9,12,13,14
2,4,6,9,15
0,1,6,9,15
3,5,6,9,15
1,4,5,9,15
1,2,8,9,15
3,4,8,9,15
2,5,7,9,15
0,4,7,9,15
1,3,7,9,15
1,3,5,8,15
0,2,4,8,15
1,5,6,7,15
3,4,6,7,15
4,5,7,8,15
0,2,3,9,15
2,3,7,8,15
0,1,7,8,15
0,5,6,8,15
1,4,6,8,15
0,6,8,13,14
3,7,8,13,14
2,4,8,13,14
7,8,11,12,14
2,5,11,12,14
1,4,11,12,14
0,3,4,13,14
1,2,5,13,14
0,10,11,12,14
3,9,11,12,14
3,5,11,13,14
1,8,11,13,14
0,7,11,13,14
4,6,11,13,14
4,7,9,13,14
1,3,9,13,14
0,2,9,13,14
4,5,10,13,14
6,7,10,13,14
0,1,2,3,5
2,3,10,13,14
0,1,10,13,14
5,8,9,13,14
0,2,11,13,17


j'ai utilisé pmc https://github.com/vrothberg/troll/tree/master/pmc qui retourne le res en 37sec

la generation du mtx est fait par
Code: Tout sélectionner
const k = 5;
const n = 18;
const t = 3;//at most t (included)
function generateCombi(k,n){
    var Combinatorics = require('js-combinatorics');
    var v = new Array(n).fill(0).map((x,i)=>i)
    cmb = Combinatorics.combination(v, k);
    var cs = [];
    while(a = cmb.next()) {
        cs.push(new Set(a));
    }
    return cs;
}
function cross(a,b){
    var count = 0;
    [...a].forEach(el=>{
        if(b.has(el)){
            count++;
        }
    })
    return count <= t;
}
var util = require('util');
var fs = require('fs');
function buildMat(cs, outname, cbk){
    var f = fs.createWriteStream(outname);
    var i = 0;
    var j = 0;
    var count = 0;
    function next(){
        if(j == i){
            if(i%100==0){
                console.log('done ', i,' of ', cs.length)
            }
            j = 0;
            i++;
        }
        if(i == cs.length){
            f.close();
            return f.on('close', function(){
                return cbk(null, count);   
            })
        }
        var c1 = cs[i];
        var c2 = cs[j];
        var bool = cross(c1, c2);
        var callNext = false;
        if(bool){
            count++;
            f.write([i, j, 1].join(' ')+'\n') && (callNext = true);
        }else{
            callNext = true;
        }
        ++j;
        if(callNext){next()}
    }
    f.on('drain', function(){
        next();
    });
    next();
}
if(!module.parent){
    var cs = generateCombi(k,n);
    const tmpName = './tmp.txt';
    Promise.all([
        util.promisify(buildMat)(cs,tmpName).then(nLines=>{
            const fd = fs.openSync('output.mtx', 'w+')
            var s = [
                '%%MatrixMarket matrix coordinate pattern symmetric',
                [cs.length-1, cs.length-1, nLines].join(' ')
            ].join('\n')
            const insert = Buffer.from(s+'\n')
            fs.writeSync(fd, insert, 0, insert.length, 0)
            const data = fs.readFileSync(tmpName)
            fs.writeSync(fd, data, 0, data.length, insert.length)
            return new Promise(function(resolve, reject){
                return fs.close(fd, (err) => {
                    if (err) reject(err);
                    return resolve();
                }); 
            }).then(_=>console.log('written output.mtx'))
        }),
        util.promisify(fs.writeFile)('./ref.json', JSON.stringify(cs.map((x,i)=>[...x])))
            .then(_=>console.log('written ./ref.txt'))
    ])
}else{
    module.exports = {
        cross:cross
    }
}


et la restituion des combinaison par
Code: Tout sélectionner
var fs = require('fs');
var ref = require('./ref.json')
var argv = process.argv.splice(2);
var file = 'test.txt';//of format id1 id2 id3...
var ids = fs.readFileSync(file).toString().trim().split(' ');
var combis = ids.map(id=>{
    var c = ref[id];
    if(!c){
        throw 'unknown combi for id '+id;
    }
    return {id:id, s:new Set(c)};
});
var mmformat = require('./mmformat');
for(var i = 0; i<combis.length; ++i){
    var c1 = combis[i];
    for(var j = i+1; j<combis.length; ++j){
        var c2 = combis[j];
        var bool = mmformat.cross(c1.s, c2.s);
        if(!bool){
            throw `combi do not intersect (${[...c1.s]}|${[...c2.s]}) ids: ${c1.id},${c2.id}`
        }
    }
}
console.log('ok')
console.log(combis.map(x=>[...x.s].join(',')).join('\n'))


le fichier test.txt attendu contient
Code: Tout sélectionner
5673 5641 5857 5401 5436 5334 5377 5548 5549 5587 5572 5466 6235 6184 6356 6383 6276 6258 6313 5928 5977 5987 5879 5885 5891 5918 5905 6084 6122 6100 6099 6020 5993 6052 6038 4612 4652 4548 4587 4590 4734 4780 4668 4385 4378 4367 4316 4297 4504 4497 4420 4427 4410 4457 4439 4433 5141 5190 5170 5166 5087 5075 5098 5290 5325 5220 5199 5244 5256 5258 5231 5228 4891 4894 4810 4806 5027 4998 4996 5055 5037 5028 4959 4942 4990 4965 7852 7839 7877 7774 7802 7798 7988 8001 7954 7947 7938 7542 7720 7704 7751 7758 7736 7647 7687 7695 8398 8371 8419 8414 8507 8565 8548 8539 8450 8442 8478 8474 8471 8106 8163 8138 8048 8043 8041 8035 8093 8081 8070 8261 8298 8271 8185 8167 8222 8230 8231 8210 8204 6757 6786 6767 6674 6722 6713 6700 6698 6871 6898 6876 6830 6833 6514 6494 6403 6399 6391 6446 6429 6427 6655 6632 6528 6527 6590 6568 6567 7296 7360 7334 7276 7267 7264 7470 7463 7400 7395 7030 7011 7057 7046 6957 6964 6970 6948 7002 7168 7164 7214 7209 7203 7200 7195 7116 7100 7090 7088 7158 7140 7132 1419 1404 1345 1341 1391 1370 1530 1562 1485 1468 1508 1135 1144 1183 1127 1312 1325 1327 1310 1217 1197 1231 1996 1980 1971 1887 1871 1918 2113 2030 2011 2052 2064 1732 1707 1618 1611 1603 1600 1642 1634 1808 1845 1739 1796 1800 1782 1772 337 376 367 511 416 427 402 99 80 113 7 54 222 207 249 265 153 138 170 869 912 908 826 808 852 838 831 1018 1004 1046 1058 1039 1034 939 982 994 978 969 966 622 611 640 633 565 544 536 588 596 575 570 764 742 732 790 796 769 679 666 719 725 729 707 702 699 3478 3508 3667 3677 3716 3701 3610 3657 3639 3637 3286 3324 3330 3213 3236 3416 3458 3464 3359 3344 4122 4038 4229 4200 4212 4246 4256 4239 4140 4136 4133 4177 4169 3862 3846 3837 3750 3734 3792 3941 3988 3975 3968 3965 3892 3874 3867 3924 3911 3906 3899 2405 2448 2625 2628 2635 2554 2566 2546 2535 2587 2583 2569 2251 2248 2238 2157 2146 2189 2184 2178 2174 2356 2387 2398 2376 2369 2288 2271 2270 2331 2334 2313 2306 2303 3017 3021 3005 3051 3059 3044 2960 2947 2936 2990 2979 3157 3149 3162 3146 3187 3194 3176 3170 3168 3087 3078 3069 3067 3122 3131 3113 3108 3103 3100 2788 2797 2781 2697 2674 2669 2724 2729 2707 2701 2895 2911 2903 2901 2826 2805 2802 2851 2864 1 2842 2837 2834 7069

(output de pmc)
la vie est une fête :)

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

Re: Combinatoire

par fatal_error » 10 Juil 2019, 16:48

pas mieux mais juste qq mots clés...
le graphe obtenu est régulier, et en particulier a pour nom graphe de kneser generalisé

pour 3,5,15, vu que 3003 vertex et w(GK)=E(3003/5) ~= 600 pour GK le graphe de kneser, il y a au moins ca pour GKs.

une piste est ptet de voir si une plus grande clique est trouvée par cuda-ms ou rmc (qui ont l'air de moins souffrir sur les graphes de 3k+ noeuds) et comparer avec un bound pour GK_s (j'imagine que des matheux en ont donné/démontré qq1 pour (15,5,3) et (18,5,3))
la vie est une fête :)

Juz2k19
Messages: 1
Enregistré le: 09 Aoû 2019, 18:27

Re: Combinatoire

par Juz2k19 » 19 Aoû 2019, 11:25

fatal_error a écrit:pas mieux mais juste qq mots clés...
le graphe obtenu est régulier, et en particulier a pour nom graphe de kneser generalisé

pour 3,5,15, vu que 3003 vertex et w(GK)=E(3003/5) ~= 600 pour GK le graphe de kneser, il y a au moins ca pour GKs.

une piste est ptet de voir si une plus grande clique est trouvée par cuda-ms ou rmc (qui ont l'air de moins souffrir sur les graphes de 3k+ noeuds) et comparer avec un bound pour GK_s (j'imagine que des matheux en ont donné/démontré qq1 pour (15,5,3) et (18,5,3))


ok c'est possible qu'un matheu passe ici pour pour (15,5,3) et (18,5,3) ?

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

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