[complexe] obtenir toutes les combinaisons

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. Salutation !
Char Snipeur

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 Salutation !
Char Snipeur

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. tafiscobar "lou waye def bopame"
la nullite n'existe pas, l'ignorance oui, ah je suppose!!!

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. Salutation !
Char Snipeur

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.

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+

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. Salutation !
Char Snipeur

Bonjour,

il manque le 4, 3,1 pour 8.

as-tu un code pour afficher les combinaisons?

A+

Salut,

dès que j'ai vu ce thread j'ai pensé à une équation diophantienne linéare
http://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}++;
        }
       }
      }
     }
    }
   }
  }
 }
}
$,="\n";
print sort keys %hash,"\n";
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#

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,"\n";
          #$rrr="";
          $hash{$chaine}++;
       }
      }
     }
    }
   }
  }
 }
}
}
$,="\n";
print sort keys %hash,"\n";
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.

ibase = 16

f256 = FF578F57C15BB743BEAA77D27637E02B598DFFA9AEBD15889187FE6EB3BD­CA516C3FA1A52EABEF31F33B4B8C2E5B5524F1AA4F3329393912F40DBBE2­3D7F39723E0BE05B6696B11F8EEA0ABE365A11D9F2735AC7E5B4E015AB19­B35B84893685B37A9A0A62A566D6571D7E00D4241687F5C804F37CDE9BF3­11C0781F51CC007C5A01A94F6CFCECEA640B8E9AB7BD43E73E5DF5D0E1EE­B4D9B6CC44BE67B7CAD80808B17869561B579FFE0BBDECA5C83139E45800­000000000000000000000000000000000000000000000000000000000000­0

ibase = A

/*define f (x) {
	if (x <= 1) return (1);
	return (f(x-1) * x);
}*/

define f (x) {
auto f
f = 1
while (x > 1)
	f *= x--
return f
}

define mytreatment (freqs[], size) {
	// NO PUBLICY RELEASED
	return 0
}

define denomb(freqs[], size)
{
	auto freqsfreqs[], indexfreqs[], done, divisfreqsfreqs, divisfreqs, res1, res2, countdff
	for(i = 0; i < size; i++)
	{
		done = 0
		for(j = 0; j < size; j++)
		{
			if (indexfreqs[j] == freqs[i])
			{
				freqsfreqs[j] += 1 
				done = 1
				break
			}
		}
		if (done == 0)
		{
			for(j = 0; j < size; j++)
			{
				if (freqsfreqs[j] == 0)
				{
					freqsfreqs[j] += 1
					indexfreqs[j] = freqs[i]
				}
			}
		}
	}
	countdff  = 0
	res1 = f256
	for(i = 0; i < size; i++)
		if (freqsfreqs[i] != 0)
		{
			temp = f(freqsfreqs[i])
			res1 /= temp
			countdff += 1
		}
	res1 /= f(size - countdff)
	res2 = f256
	for(i = 0; i < size; i++)
		if (freqs[i] != 0)
		{
			res2 /= f(freqs[i])
		}
/*	print res1, " * ", res2, "\n" */
	return (res1 * res2);
	
}


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
/*	ent = mytreatment(a[], size) */
/*	quant = denomb(a[], size) */
	totalcomb += quant
	if (checkpoint)
	{
		for(i = 0; i < size; i++)
			print a[i], ","			print "_\n"
		print "counter : ", countfreqcomb, "\n"
		print "LAST : ", quant, "\n"
		print "TOTALCOMB : ", totalcomb, "\n"
	}
	oldent = ent
	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
			}
			for(k = 0; k < size; k++)
				print a[k], ","				
                                print "_\n"
			print "verif i :", i, "\n"*/
		}
	}
}	

if (totalcomb == maxcomb)
{
	print "OK = ", maxcomb, "\n"
} else
{
	print "KO -> ", totalcomb, " != ", maxcomb, "\n"
	print "bitdist -> ", l(totalcomb)/l(2), " ?= ", l(maxcomb)/l(2), "\n"
	print "Diff -> ", totalcomb - maxcomb, "\n"
}
quit

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!!!

Bonjour à tous,

2h30 de calcul pour le (13, 256).

179 952 501 063 combinaisons

A+

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+

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

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

#include <stdio.h>


unsigned long long g(unsigned int a,unsigned int b, unsigned int c)
{
  unsigned long long res = 0;
  if (a == 2)
  {
    res = (b / a) - c + 1;
  }
  else
  {
    unsigned long limit = (b / a);
    for(unsigned int i = c; i < limit; i++)
    {
      res = res + g(a - 1, b - 1, i);
    }
  }
  return res;
} 

unsigned long long denombre(unsigned int n, unsigned int p)
{
  unsigned long long res = 0;
  for(unsigned int k = 3; k < n; k++)
  {
    unsigned long limit = (p / k);
    for(unsigned int i = 1; i < limit; i++)
      res = res + g(k - 1, p - i, i);
  }
  res = res + 1 + (p / 2);
  return res;
}

int main(int argc, char** argv)
{	
  unsigned int a = 13 ;
  unsigned int b = 256;
  printf("denombre (%d,%d) = %llu\n", a, b, denombre(a, b));
  return 0;	
}

#include <stdio.h>


unsigned long long g(unsigned int a,unsigned int b, unsigned int c)
{
  unsigned long long res = 0;
  if (a == 2)
  {
    res = (b / a) - c + 1;
  }
  else
  {
    unsigned long limit = (b / a);
    for(unsigned int i = c; i <= limit; i++)
    {
      res = res + g(a - 1, b - i, i);
    }
  }
  return res;
} 

unsigned long long denombre(unsigned int n, unsigned int p)
{
  unsigned long long res = 0;
  for(unsigned int k = 3; k <= n; k++)
  {
    unsigned long limit = (p / k);
    for(unsigned int i = 1; i <= limit; i++)
      res = res + g(k - 1, p - i, i);
  }
  res = res + 1 + (p / 2);
  return res;
}

int main(int argc, char** argv)
{       
  unsigned int a = 13 ;
  unsigned int b = 256;
  printf("denombre (%d,%d) = %llu\n", a, b, denombre(a, b));
  return 0;     
}

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)

tafiscobar "lou waye def bopame"
la nullite n'existe pas, l'ignorance oui, ah je suppose!!!

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+