Algorithme: Fonction récursive de partition d'un ensemble et temps de calcul
Bonjour,
Je cherche à écrire une fonction partition(n) qui prend en argument un entier (n = nombre d'élements) et qui renvoie une matrice représentant tous les sous ensembles possibles avec des 0 et des 1 (si un élement est dans le sous ensemble on lui affecte 1,0 sinon).
Le nb de sous ensemble d'un ensemble à n élements est 2^n, donc partition(n) est une matrice de taille n*2^n (ca grossit très vite).
Je ne suis pas du tout familier avec la syntaxe VBA et mes souvenirs d'informatique sont assez anciens mais j'ai réussi à écrire un algorithme trivial qui fonctionne, le code est le suivant.
La fonction est récursive:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| Function Partition(n_elem As Integer) As Variant
Dim Tab_temp(1024, 1024) As Integer
If n_elem = 1 Then
Tab_temp(0, 0) = 0
Tab_temp(0, 1) = 1
Else
For k = 0 To 2 ^ (n_elem - 1) - 1
Tab_temp(0, k) = 0
Tab_temp(0, 2 ^ (n_elem - 1) + k) = 1
Next k
For i = 0 To n_elem - 2
For k = 0 To 2 ^ (n_elem - 1) - 1
Tab_temp(i + 1, k) = Partition(n_elem - 1)(i, k)
Tab_temp(i + 1, 2 ^ (n_elem - 1) + k) = Partition(n_elem - 1)(i, k)
Next k
Next i
End If
Partition = Tab_temp
End Function |
J'étais content, jusqu'à ce que je me rende compte que pour n=4 ca met déjà plusieurs secondes à s'exécuter... j'en ai pas besoin pour des valeurs très elevées de n (jusqu'à n=6/7) mais ca prendra trop de temps à tourner car je l'utilise plusieurs fois cette fonction après.
Donc j'essaye d'optimiser la syntaxe de la fonction.
Je pense que ce qui prend du temps c'est que je calcule beaucoup de fois Partition(n_elem-1) dans mes boucles. Donc j'ai essayé de stocker dans un tableau temporaire la valeur Partition(n_elem-1) et appeler ce tableau temporaire:
> temp_part = Partition(n_elem-1)
et appeler temp_part(i,k) dans la suite du code mais ça me met "erreur d'exécution 7: mémoire insuffisante.
Est-ce qu'une âme charitable peut m'aider pour faire marcher tout ça plus rapidement?
Aussi, peut-on créer des tableaux de dimension variable genre Tab(n_elem) par exemple? Je n'ai pas l'impression que ce soit possible. Lié à ça, un mystère est que le nombre d'initialisation de la matrice Dim Tab_temp(1024, 1024) joue énormément dans la vitesse de calcul je ne sais pas pourquoi car je boucle seulement sur les éléments qui m'intéressent.
Merci d'avance pour vos conseils éclairés
