[complexe] obtenir toutes les combinaisons

Question

Bonjour,
voici le casse-tête sur lequel je suis.
J'ai 256 cases, 256 billes, je peux mettre autant de billes que je veux par case (mais n'excedant jamais un total de 256)
Je veux passez en revue toutes les combinaisons possibles en sachant que l'on ne distingue pas les cases entre-elles ni les billes entre elles (donc pas d'ordre), juste leurs quantités par cases.
exemples:
0 0 0 0 ... 1 255
0 0 0 0 ... 2 254
...
0 0 0 0 ... 1 1 254
0 0 0 0 ... 43 52 161
( on ne peut pas faire 0 0 0 0 ... 254 1 1 , il est deja present dans l'exemple)

si quelqu'un avait le debut du bout d'une bonne piste... parce que la je commence à surchauffer dans mes diverses tentatives...

merci d'avance

PS: bon le top du top serait de trouver un truc generique pour n billes et n cases... mais bon déjà comme çà c'est violent...

Afficher la suite

Char Snipeur · Answer

salut.J'ai pas la réponse, mais je voi deux pistes, que tu as surment déjà essayer :- essai en disernable, c'est à dire en distinguant boite et bille, puis compter le nombre de cas que tu compte plusieurs fois.- faire comme tu dit avec n , mais commence par n=2, puis 3 puis 4 ...jusqu'à temps que tu trouve une loi de comptage. Essai toute les numération habituel :  les puissances, les factoriels, les combinaison (Cn et An)intuitivement, je penche pour une somme de CnBonne chance.

Char Snipeur · Answer

SalutJ'ai fait les premiers essais pour n=:1->1 combinaison2->2 combinaisons3->34->55->76->117->15ce qui laisse supposer la relation suivante , pour n impaire :N(n)=N(n-2)+2^((n-1)/2) combinaisons.pour n pair :la relation me saute pas aux yeux, il faudrait faire pour n=8je pense que :N(n)=N(n-1)+(N(n-3)-N(n-4))*2Je continue à reflechir.Dit moi ou toi tu en est

tafiscobar · Answer

salut tu peux considérer ton probléme comme la résolution de ce probléme: Soit n et on a : 1 + 1 + 1 +... + 1 = n, quel est le nombre de façons de regrouper les 1 en a_1,...a_p tel que a_1 + ...+a_p = n. Tu peux trouver la solution dans des livres de combinatoire pour licence. J'ai oublié la formule.

Char Snipeur · Answer

En effet, après avoir creuser un peu plus, je me suis rendu compte que c'était plus compliquer qu'il n'y parait:8->219->2810->42Donc suite très bizard.Et comme tafiscobar, j'ai remarqué que c'etait toutes les façons d'écrire n en somme unique.

realdar · Answer

Bon je cherche à obtenir toutes les combinaisons (generer la suite en fait), ce que je viens de finir par reussir. Enfin maintenant il faut que j'attende lundi (j'ai mis ca a calculer sur une machine de mon taff pendant le weekend, lol)Par contre calculer le nombre total de combinaison  m'interresse enormement.Actuellement j'ai un moyen qui est un peu tirer par les cheveux mais qui devrait marcher. En fait cette suite representent toutes les fréquences de chaque octets(y en a 256, de 0 à 255)  dans chaque fichier imaginable de 256 octets... donc pour chaque element de la suite je calcule le nombre permutations de l'element * par le nombre de permutations de ce que représente l'element, en faisant la somme je dois obtenir 2^(8*256).par exemple:0 0 0 ... 4 10 10 10 127 127ca donne : (256! / (1! 3! 2! (256-6)! )) * (256! / (4! 10! 10! 10! 127! 127!))Mon but est de faire un 'certain traitement' sur chacun des élements de ma suite. ce traitement me donnant un résultat numérique, et je calcule sur combien de fichiers de 256octets ca s'applique...Le but étant de "cartographier" certaines propriétés des 'grands fichiers'. le 256octets est arbitraire, je pourrais prendre plus grand ou plus petit (mais plutot plus grand... ce que je ferais après, pour voir si "l'image" obtenue est sensiblement la même). Bon puis je n'allais pas generer 2^(8*256) combinaison de 256octets, la c'est pas un weekend qu'il m'aurait fallut mais plusieurs années.Mais si j'avais présenté les choses comme çà, je ne suis pas sur que çà aurait été très clair. :)bon ca donne des temps de calcul un peu gigantesques mais "raisonables".Enfin pour verifier tout çà, de façon apriori, il me manque le moyen de calculer la taille de cette suite. Bon je vais voir si je peux essayer de trouver un truc par rapport à ce que vous m'avez donnez comme pistes... mais trouver un livre de license, ca va pas etre evident...enfin si vous avez d'autres idées je suis preneur.

JvDo · Answer

bonsoir,après avoir fait une routine mi-récursive pour calculer le nombre de combinaisons possibles, je tombe sur des valeurs qui grimpent vite vers le déraisonnable, aussi vite que le temps de traitement!je me suis arrêté à 128 ( 4 351 078 600)de 3 à 100 ça donne : 3    5    7    11    15    22    30    42    56    77    101    135    176    231    297    385    490    627    792    1 002    1 255    1 575    1 958    2 436    3 010    3 718    4 565    5 604    6 842    8 349    10 143    12 310    14 883    17 977    21 637    26 015    31 185    37 338    44 583    53 174    63 261    75 175    89 134    105 558    124 754    147 273    173 525    204 226    239 943    281 589    329 931    386 155    451 276    526 823    614 154    715 220    831 820    966 467    1 121 505    1 300 156    1 505 499    1 741 630    2 012 558    2 323 520    2 679 689    3 087 735    3 554 345    4 087 968    4 697 205    5 392 783    6 185 689    7 089 500    8 118 264    9 289 091    10 619 863    12 132 164    13 848 650    15 796 476    18 004 327    20 506 255    23 338 469    26 543 660    30 167 357    34 262 962    38 887 673    44 108 109    49 995 925    56 634 173    64 112 359    72 533 807    82 010 177    92 669 720    104 651 419    118 114 304    133 230 930    150 198 136    169 229 875   j'ai du stopper le calcul pour 256 après 6h de traitement qui n'avançait guère.mes routines :Function dénombre(n, p)For k = 3 To n    For i = 1 To Int(p / k)        dénombre = dénombre + g(k - 1, p - i, i)    NextNextdénombre = dénombre + 1 + Int(p / 2)End FunctionFunction g(a, b, c)If a = 2 Then    g = Int(b / a) - c + 1Else    For i = c To Int(b / a)        g = g + g(a - 1, b - i, i)    NextEnd IfEnd Functionje vais laisser le pc tourner cette nuit pour voir...A+

Char Snipeur · Answer

Je suis étonner qu'on trouve différent pour 8 et 9...j'ai pour 8:8							7	1						6	2						5	3						4	4						6	1	1					5	2	1					4	2	2					3	3	2					5	1	1	1				4	2	1	1				3	3	1	1				3	2	2	1				2	2	2	2				4	1	1	1	1			3	2	1	1	1			2	2	2	1	1			3	1	1	1	1	1		2	2	1	1	1	1		2	1	1	1	1	1	1	1	1	1	1	1	1	1	1Je ne voi pas lequel j'ai oublié.Moi je procede en fesant des piles : je rempli celle qui est le plus à gauche, et je distribu ensuite vers la droite. en conservant le fait que celle de gauche doit au moins être égale à celle de droite. comme ça j'en compte pas deux fois.

JvDo · Answer

Bonjour,il manque le 4, 3,1 pour 8.as-tu un code pour afficher les combinaisons?A+

lami20j · Answer

Salut,dès que j'ai vu ce thread j'ai pensé à une équation diophantienne linéarehttps://fr.wikipedia.org/wiki/%C3%89quation_diophantiennenA+nB+............+nIV= 256Ne reste qu'à trouver toutes les inconnues A...IV.J'ai pris un exemple que j'ai trouvé dans le livre Maîtrise des expressions regulières - Edition O'Reilly est j'ai adapté pour cette situation.En fait je ne vais pas travailler avec des nombres mais avec des chaînes de caractères.Pour eviter les doublons je fait un tri des chaînes et puis je construis un hash en utilisant comme clés les chaînes.Vu que les clés sont uniques j'obtiens les combinaison sans doublon.Ca m'evite de faire un procédure pour calculer les permutations, qui prendra encore plus de temps.J'ai fait un test (processeur AthlonXP 1200, 256 DDR) pour 8.Le programme  tourne beaoucoup puisque d'abord il cherche toutes les posibilités et ensuite il elimine les doublons. Pour 8 avec les doublons on a 58 combinaison et 22 sansPour 256, je pense à construire la chaîne et l'exécuter avec evalJe ne suis pas sur si ça va marcher.Je vais utiliser la notation des colonnes qu'on trouve sous Open Office ( de A à IV) Je dois trouver un moyen d'optimiser le calcul - 10 minute que pour 8 c'est trop, mieux faire à la main ;)debian:/home/lami20j/trash# cat combinaison.pl#!/usr/bin/perluse warnings;use strict;my (%hash);my ($a,$b,$c,$d,$e,$f,$g,$h);for my $aa(1..8){ for my $bb(1..8){  for my $cc(1..8){   for my $dd(1..8){    for my $ee(1..8){     for my $ff(1..8){      for my $gg(1..8){        for my $hh(1..8){        if (($a,$b,$c,$d,$e,$f,$g,$h) =         (('o' x 16) =~ /^(o{0,$aa})\1(o{0,$bb})\2                          (o{0,$bb})\3(o{0,$dd})\4                          (o{0,$ee})\5(o{0,$ff})\6                          (o{0,$ee})\7(o{0,$ff})\8$/x)) {          ($a,$b,$c,$d,$e,$f,$g,$h) = (length($a),length($b),                                       length($c),length($d),                                       length($e),length($f),                                       length($g),length($h));           my $chaine = join("",sort split //,"$a$b$c$d$e$f$g$h");           $hash{$chaine}++;        }       }      }     }    }   }  } }}$,="
";print sort keys %hash,"
";debian:/home/lami20j/trash# time perl combinaison.pl00000008000000170000002600000035000000440000011600000125000001340000022400000233000011150000112400001133000012230000222200011114000111230001122200111113001111220111111211111111real    10m33.554suser    9m43.828ssys     0m2.876sdebian:/home/lami20j/trash#

lami20j · Answer

Re,je reviens avec une optimisation ( de10 minute qui est énorme le script fine dans moins de 3 secondes )debian:/home/lami20j/trash# cat combinaison.pl#!/usr/bin/perluse warnings;use strict;my (%hash);my ($a,$b,$c,$d,$e,$f,$g,$h);for my $aa(1..8){for my $bb(1..7){ for my $cc(1..6){  for my $dd(1..5){   for my $ee(1..4){    for my $ff(1..3){     for my $gg(1..2){       for my $hh(1){       if (($a,$b,$c,$d,$e,$f,$g,$h) =        (('o' x 16) =~ /^(o{0,$aa})\1(o{0,$bb})\2                         (o{0,$bb})\3(o{0,$dd})\4                         (o{0,$ee})\5(o{0,$ff})\6                         (o{0,$ee})\7(o{0,$ff})\8$/x)) {         ($a,$b,$c,$d,$e,$f,$g,$h) = (length($a),length($b),                                      length($c),length($d),                                      length($e),length($f),                                      length($g),length($h));          my $chaine = join("",sort split //,"$a$b$c$d$e$f$g$h");          #my $rrr = $chaine;          #next if $chaine eq $rrr;          #print $chaine,"
";          #$rrr="";          $hash{$chaine}++;       }      }     }    }   }  } }}}$,="
";print sort keys %hash,"
";debian:/home/lami20j/trash# time perl combinaison.pl00000008000000170000002600000035000000440000011600000125000001340000022400000233000011150000112400001133000012230000222200011114000111230001122200111113001111220111111211111111real    0m2.643suser    0m2.612ssys     0m0.012sdebian:/home/lami20j/trash#lami20jP.S. toujours pour 8J'ai déjà écrit le code pour generer les 256, je vais laisse tourner cette nuit pour voir.

JvDo · Answer

Bonjour,merci pour le code mais je ne suis pas sûr de pouvoir l'adapter à mon VBA. enfin, je vais voir.pour ton estimation de combinaisons, je crains que tu ne sois optimiste.j'ai fais une projection linéaire sur les différences, projection qui me laisse penser à un nombre de l'ordre des 30 millions de milliards (c'est pas du capitaine Haddock puisqu'il n'y a pas les sabords!)explication de la projection :si tu regardes les différences de combinaisons (sur les 10 dernières des 100 premières) tu verras qu'il y a sensiblement un facteur 3 entre la 100ème et la 90ème.je prends les 10 dernières parce que la courbe s'excite comme une exponentielle fatiguée ou plutôt comme une puissance de quelque chose.donc je projette linéairement sur les différences jusque 256 et je somme.j'ai encadré (ça, c'est ce que j'aime à croire) la cible avec une projection de toujours le même facteur 3 mais sur la 89ème valeur au lieu de la 90ème et je tape toujours les 30 millions de milliards.bref, ça fait beaucoup de week-ends !pour le nombre de combinaisons du traitement du week-end tu dois être au moins au nombre de combinaisons (13,256) vu que tu es arrivé au début des (14,256).je suis en train de calculer le (13,256) mais ça mouline très, très lentement.dès que j'ai le résultat des courses, je te tiens au courant.A+PS: tout ce que je viens de dire ne tient que si mon algo de comptage est juste!!!

JvDo · Answer

Bonjour à tous,2h30 de calcul pour le (13, 256).179 952 501 063 combinaisonsA+

JvDo · Answer

Bonsoir,le module VBA de listage des combinaisons fonctionne.les 37 338 combinaisons du (40,40) s'affichent en 7s après 2s d'initialisation.les 63 261 combinaisons du (43,43) s'affichent en 11s après 2s d'initialisation.je n'ai pas géré le changement de feuille au delà des 65 535 lignes.reste à savoir ce que je vais faire de ces bouts de code....A+

realdar · Answer

Salut JvDo, voila l'algo épuré pour pouvoir le traduire en VB tu peux mettre checkpoint à 1 tout le temps pour afficher toutes les combinaisons. J'ai l'impression soit que tu en comptes trop, soit que j'en compte pas assez... size = 256 for(i = 0; i < size; i++) { a[i] = 0 } nbelem = 256 a[size-1] = nbelem nbelemused = 2; checkpoint = 0 countfreqcomb = 0 while(1) { countfreqcomb += 1 if (checkpoint) { for(i = 0; i < size; i++) print a[i], "," print "_ " print "nombre de combinaison : ", countfreqcomb, " " } if (a[size-1] == 1) { break } checkpoint = 0 for(i = size - 2; i >= 0; i--) { if ((a[i]+1) < a[i+1]) { a[i] += 1 a[i+1] -= 1 break } else { if (a[i-1] > 0) { newval = a[i-1] + 2 } else { for(j = size - nbelemused; j < size - 1; j++) { a[size-1] += a[j]-1 a[j] = 1 } a[i-1] = 1 a[size-1] -= 1 nbelemused += 1 checkpoint = 1 break } if ((newval-1) > a[i]) { /* do nothing */ } else { a[i+1] += (a[i]-newval) a[i] = newval } } } } quit

JvDo · Answer

Bonjour,je viens d'essayer d'adapter ton code en VBA.je l'ai testé avec size=nbelem=20.j'ai mis checkpoint à 1 pour avoir l'affichagej'obtiens des choses potentiellement bizarres au niveau de la séquence des résultat, à la fois des doublons, à la fois des trous.exemple de doublon :0_6_7_70_7_7_61_1_1_17ou0_3_5_6_60_3_6_6_5exemple de trou :		1_6_6_72_2_9_7as-tu ce genre de chose ou est-ce mon adaptation du code qui laisse à désirer?Le test de fin if (a[size-1] == 1) {break} empêche le programme d'aller au delà de 0_2_3_4_4	_5_20_2_3_4_5_5_1cordialement

tafiscobar · Answer

salut, je n'ai pas le temps de le coder ou de le faire, mais le nombre de combinaisons est exponentiel. Ensuite, il faut utiliser de la programmation dynamique et non du récursif sinon tu ne t'en sortiras pas (tu vas calculer la meme chose plusieurs fois et ce n'est pas intéressant).  Un livre de licence ne devrait pas etre difficile a trouver (dans une bibliotheque universitaire)

JvDo · Answer

Bonjour à tous,il ya une différence sur les premières lignes de (256,256) :avec ton code mis en VBA :0_0_0_1_83_86_860_0_0_1_84_84_870_0_0_1_84_85_860_0_0_1_85_85_850_0_0_2_2_167_850_0_0_2_3_3_2480_0_0_2_3_4_2470_0_0_2_3_5_246ça devrait être :0_0_0_1_84_85_860_0_0_1_85_85_850_0_0_2_2_2_2500_0_0_2_2_3_2490_0_0_2_2_4_248c'est tout ce que j'ai trouvé sur les 12.000 premières lignes.as-tu testé en modifiant nbelem et size?A+

realdar · Answer

Hello, JvDo, tu as raison mon algo etait buggé. voici l'algo corrigé mais y a encore quelque chose de différent avec ton dénombrement et je n'ai pas trouvé ce qui clochait. ca marche bien pour (3,256) => 5589 mais je trouve avec ton algo : (4,256) => 123464 avec mon enumeration : (4,256) => 123485 size = 256 maxcomb = 2 ^ (size * 8) for(i = 0; i < size; i++) { a[i] = 0 } nbelem = 256 a[size-1] = nbelem oldent = 0 totalcomb = 0; nbelemused = 2; divisor = nbelem / nbelemused; checkpoint = 0 countfreqcomb = 0 while(1) { countfreqcomb += 1 if (checkpoint) { for(i = 0; i < size; i++) print a[i], "," print "_ " print "counter : ", countfreqcomb, " " } if (a[size-1] == 1) { break } checkpoint = 0 for(i = size - 2; i >= 0; i--) { if ((a[i]+1) < a[i+1]) { a[i] += 1 a[i+1] -= 1 break } else { newval = a[i-1] + 2 if ((i == size-1) || (newval-1) > a[i]) { /* do nothing */ } else { a[i-1] += 1 if (a[i-1] == 1) checkpoint = 1 newtot = -1 for(k = i; k < size; k++) { if ((k == size-1) || (a[k]+1 < a[k+1])) { a[k] += newtot break } else { newtot += a[k] - (newval - 1) a[k] = newval - 1 } } break } } } } est-ce que tu pourrais mettre ton code d'enumeration ici que je puisse voir ce qui cloche dans mon nouvel algo.

realdar · Answer

Par contre,ton algo de denombrement va à vitesse grand V en C...Pour (13,256) je n'ai mis que 5minutes pour trouver la même valeur que toi.

JvDo · Answer

Bonjour,il va falloir que je me mette au C!!!!A+

realdar · Answer

Merci pour ton algo d'énumération. Je n'ai pas eu le temps de tester et de corriger mon algo cette fin de semaine, ni ce weekend.
J'espere pouvoir la semaine prochaine.
En tout cas. Je te remerci vraiment.

brx · Answer

L'année 2006, c'était hier :-) 

On utilise ici une fonction récursive qui reçoit deux arguments : 
1) le nombre de billes à combiner 
2) le nombre max de billes à mettre dans le trou qui en contient le plus 

Ainsi pour trouver f(4), on boucle de 1 à 4 et on liste les solutions : 
f(3,1) suivit de "1" -> 1 1 1 1 
f(2,2) suivit de "2" -> 1 1 2 et 2 2 
f(1,1) suivit de "3" -> 1 3 
et "4"                     -> 4 

Une variable %cache permet de ne pas recommencer des calculs déjà réalisés. 


#perl 
use strict; 

my %cache; 
sub f { 
 my ($n,$max) = (shift,shift); 
 $max = $n if (not defined $max); 
 $max = $n if $max>$n; 
 return "1" if ($n == 1); 
 my @res; 
 for my $i (1 .. $max) { 
  if ($i==$n) { 
   push @res, $n; 
  } else { 
   if (not defined $cache{$n-$i,$i}) { 
    $cache{$n-$i,$i} = [ &f($n-$i,$i) ]; 
   } 
   push @res, map { "$_ $i" } @{$cache{$n-$i,$i}}; 
   #push @res, map { "$i $_" } @{$cache{$n-$i,$i}};    #ordre inverse d'affichage 
  } 
 } 
 return @res; 
} 

 #Deux affichages du résultat 
my $nbbilles = 8; my @res = f($nbbilles); 
print join "
", @res; 
print "
----
"; 
print join "
", 
 map { 
  '0 'x($nbbilles - 1 - tr/ / /) #on ajoute les zéros manquants 
  .$_ 
 }   reverse @res;

[complexe] obtenir toutes les combinaisons

22 réponses

Votre réponse

Discussions similaires

Newsletters