Discussion :

[Asphator]

Bonjour,


Objectif:
Calculer le nombre de combinaisons lorsque l'on effectue un tirage de K éléments de N catégories, sachant que:
- il peut y avoir répétition
- ABB ou BAB ou BBA ne compte que pour 1 combinaison et non pas 3 (l'ordre n'a pas d'importance, mais en même temps, ce n'est pas une combinaison au sens mathématique, où justement on aurait compté 3 combinaisons)

Exemples:
exemple 1: k=4, n=2, résultat=5
AAAA
AAAB
AABB
ABBB
BBBB
exemple 2: k=2, n=4, résultat=10
AA
AB
AC
AD
BB
BC
BD
CC
CD
DD

Et ainsi de suite, avec
. k=8,n=4,résultat=165
. k=3,n=5,résultat=35
. etc...

Mon code actuel (PHP):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
<?php
 
// --- Environment configuration
sec_time_limit(0);    // no timeout after 30s
bc_scale(0);           // precision: 0 decimal
 
// --- Search values
$k=1000;                // number of columns
$n=500;                 // number of categories
 
// --- Initialization
for ($i=0; $i<$n; ++$i) {
    $data[$i]=$n-$i;
}
 
// --- Calculation
for ($i=2; $i<$k; ++$i) {
    for ($j=0; $j<$n; ++$j) {
        $next[$j]=bc_array_sum(array_slice($data,$j));
    }
    $data=$next;
}
 
// --- Display result
echo bc_array_sum($data);
 
// --- Function: sum array's big-numbers-elements
function bc_array_sum($data) {
    $sum=0;
    foreach ($data as $value) {
        $sum=bcadd($sum,$value);
    }
    return $sum;
}
?>

Pour info:
- array_slice = sous-tableau à partir de l'index <2e argument>
- bcadd = librairie bc en PHP pour les calculs sur grands nombres

Bien évidemment, avec des grandes valeurs comme k=1000 et n=500, le temps d'exécution est beaucoup trop important. Normal vu la complexité du bouzin.

J'ai du coup recours à votre aide pour savoir :
- comment s'appelle ce genre de "combinaison" (le bon terme m'aiderait dans mes recherches)
- s'il n'existerait pas une formule que j'ignore pour ce genre de "combinaisons" (mais je la trouverai sûrement s'il existe un terme précis)
- comment optimiser ce code? quelles astuces y aurait-il pour grappiller des instructions?

Merci d'avance à ceux qui se pencheront sur le problème


ps: concernant mon algorithme, ici, mon astuce est de calculer le pseudo-recursivement la longueur de mes colonnes

[Asphator]

Décidemment, poster m'aide toujours à trouver dans les minutes qui suivent.

Bon, je n'ai pas trouvé le nom, mais j'ai trouvé la formule:
(n+k-1)! / (k! (n-1)!)

[kija13]

Bonjour,

Tu aurais pu trouver la réponse encore une fois tout seul car ça s'appelle tout simplement une combinaison avec répétition
http://fr.wikipedia.org/wiki/Combina...9p%C3%A9tition