Discussion :

[phaneste]

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 :

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

[halaster08]

Bonjour,

Pour le joli code il te suffit de mettre les balise code (bouton # dans l'interface)
Pour tes questions sur les variables tableaux, notamment le fait de pouvoir faire un tableau de taille variable, je te conseille la lecture de ce tuto: https://silkyroad.developpez.com/vba/tableaux/#LII-B

[phaneste]

Merci halaster pour le lien je vais voir si je peux améliorer tout ça avec les tableaux dynamiques. En attendant j'ai trouvé la syntaxe pour sortir l'étape n-1 de la boucle (c'était tout bête je placais la variable auxiliaire au mauvais endroit) et le temps de calcul est drastiquement réduit.

[wouana19]

Bonjour,

Sympa c't histoire, bien que l'on ne connaisse pas le but de la fonction.

J'ai regardé ce que cela donnait comme résultat en l'intégrant dans une feuille Excel. peut-être qu'il y a encore plus simple, mais le résultat donne le même que vous.
et niveau vitesse d'exécution…. je vous laisse tester ^^

L'idée est que le tableau doit avoir :
- Nombre de colonne : n_elem ^ 2
- Nombre de ligne : n_elem

Ensuite il faut remplir les cellules
- pour la ligne 1, nbCol / 2 = 0, nbCol/2 = 1
- pour la ligne 2, nbCol / 4 = 0, nbCol/4 = 1
- pour la ligne 3, nbCol / 8 = 0, nbCol/8 = 1

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
36
37
38
39
40
41
42
43
44
 
Function FCpartition(n_elem As Integer) As Variant
 
   Dim C As Integer        'Nombre de colonnes
   Dim L As Integer        'Nombre de lignes
   Dim tb_temp
   Dim diviseur As Integer 'Nombre de partitions par ligne
   Dim result As Integer   'Donne un nombre entier, numéro de partition dans la ligne
 
   Dim i As Integer
   Dim y As Integer
 
   L = n_elem
 
   If n_elem = 0 Then
      MsgBox "n_elemen à 0 (zéro)", vbExclamation
      Exit Function
   End If
 
   C = 2 ^ n_elem
   ReDim tb_temp(1 To L, 1 To C)
 
   'Boucle les lignes
   For y = 1 To C
      'Boucle les colonnes
      For i = 1 To L
         diviseur = C / 2 ^ i
         'Défini le numéro de partition de la ligne
         result = WorksheetFunction.RoundUp(y / diviseur, 0)
 
         If result Mod 2 = 0 Then
            'Si numéro de partition paire
            tb_temp(i, y) = 1
         Else
            'Si numéro de partition impaire
            tb_temp(i, y) = 0
         End If
 
      Next
   Next
 
   FCpartition = tb_temp
 
End Function

J'ai modifié le nom de votre fonction car une fonction native vba s'appelle déjà Partition.

Wouana