[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...

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 "_\n"
		print "nombre de combinaison : ", countfreqcomb, "\n"
	}
	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 "_\n"
		print "counter : ", countfreqcomb, "\n"
	}
	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

Discussions similaires

Newsletters