Discussion :

[danbo52]

Bonsoir,

Je cherche pour un développement matriciel (produit de 2 matrices en particulier) pour lequel la dimension carrée est variable (2 à max capa Excel),
à produire toutes les matrices avec 0 et 1 de sorte qu'il n'y ait qu'un seul 1 par ligne et par colonne.

Exemple pour n=3 :

 ..A....B....C....D
100  010  010  100   
010  100  001  001
001  001  100  010

... etc

J'ai sur le bout des doigts l'algorithme, mais pour une dimension n, par exemple 8 ou 10, 30 ou plus, je ne parviens pas à le formuler, même si visuellement, avec la coloration des cellules, ou par l'analyse mathématique, je perçois un principe.

La raison en est que je doive me résoudre à ne jamais utiliser de boucles "for...next" imbriquées, car cette dimension de matrice est variable.

Je tente de passer par les "while...wend" qui semblent plus intéressantes dans les possibilités.

Ainsi, une matrice 6x6 doit pouvoir me permettre d'écrire 720 matrices de base avec leur 0 et 1 (on combine n! possibilités).
Tout ce que j'ai vu concernait des chaines de types "1234567" ou "ABCDEFG".
Cela ne m'intéresse pas, je travaille uniquement sur du numérique.

Mon problème est plus lié à la maitrise de l'itération plutôt qu'à l'algorithme lui-même.

Je ne cherche pas de réponse, mais une piste.... Merci à ceux qui seraient câblés autrement que moi !

[pgz]

Bonsoir

Je cherche pour un développement matriciel (produit de 2 matrices en particulier) pour lequel la dimension carrée est variable (2 à max capa Excel),
à produire toutes les matrices avec 0 et 1 de sorte qu'il n'y ait qu'un seul 1 par ligne et par colonne.

Exemple pour n=3 :
..A....B....C....D
100 010 010 100
010 100 001 001
001 001 100 010 ... etc
Merci à ceux qui seraient câblés autrement que moi !

Je pense que je suis câblé différemment car je ne comprends pas .

Je ne vois pas ce que veut dire

toutes les matrices avec 0 et 1 de sorte qu'il n'y ait qu'un seul 1 par ligne et par colonne

et ton exemple n'aide pas.

Un contre-exemple, peut-être?

Cordialement,

PGZ

[danbo52]

bonjour pgz et merci d'intervenir.

mon petit tableau d'exemple n'est peut-être pas assez clair.
Voici un exemple plus "propre" (je ne parviens pas à insérer d'images sur ce site !!!):

a) je souhaite créer une matrice 3x3 qu'avec des 0 et des 1
b) mais je ne dois trouver qu'un seul 1 dans chaque ligne
c) et qu'un seul 1 dans chaque colonne

Exemple de matrice 3x3:

1 0 0
0 1 0
0 0 1

Ici, il n'y a qu'un seul 1 dans chaque colonne et un seul 1 dans chaque ligne.

Cette matrice peut en donner 5 autres et pas plus, qui sont:

1 0 0
0 0 1
0 1 0

0 1 0
1 0 0
0 0 1

0 0 1
1 0 0
0 1 0

0 1 0
0 0 1
1 0 0

0 0 1
0 1 0
1 0 0

selon la forme n! = 3x2x1 = 6

C'est ce que je veux créer, je souhaite obtenir toutes les formes de la matrice n x n avec des 0 et des 1 selon les points a,b et c, et quelque soit la taille de la matrice.
Pour une matrice 6x6, je vais avoir 6!=6x5x4x3x21x=720 formes différentes
avec des 0 et des 1.

Ce que je souhaite faire, c'est boucler de sorte que l'algorithme me permette d'éditer toutes les matrices.

[pgz]

Bonjour.

Voilà qui est plus clair!

Le problème se ramène à un algorithme pour construire toutes les permutations de la série {1, 2, ..., n}.

En effet pour chaque permutation, on peut créer un matrice suivant la règle :

• le premier chiffre est le numéro de colonne contenant le 1 sur la première ligne
• ...
• le kième chiffre est le numéro de colonne qui contient le 1 sur la ligne k.

Reste donc à construire toutes les permutations de la série. Cela paraît simple, mais finalement cela ne l'est pas tant que ça! C'est très simple si on sait le nombre d'éléments de la série, soit la taille de la matrice carrée. On imbrique n boucles. Mais comme n est un paramètre, on est coincé.

Finalement, je ne dois pas être câblé très différemment de toi.

COmme souvent quand on a un pb de nb indéterminé de boucles imbriquées, on peut s'en tirer avec une procédure 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
24
25
26
27
28
Sub subPermutations()
Dim s1 As String, i As Integer
Const n As Integer = 4
 
For i = 1 To n
    s1 = s1 & i
Next i
 
Call subRecursive(s1, "")
 
End Sub
 
Sub subRecursive(ByVal s1 As String, ByVal s2 As String)
Dim i As Integer, s3 As String
 
s3 = s2
 
If Len(s1) = 1 Then
    s2 = s2 & s1
    Debug.Print s2 'ici on a une combinaison exploitable
Else
    For i = 1 To Len(s1)
        s2 = s3 & Mid$(s1, i, 1)
        Call subRecursive(Mid$(s1, 1, i - 1) & Mid$(s1, i + 1), s2)
    Next i
End If
 
End Sub

Pour n = 3 on obtient

123
132
213
231
312
321

J'ai l'impression qu'il devrait y avoir plus simple, mais je n'ai pas trouvé.

A partir de chaque série, il faut construire la matrice et la copier dans une feuille, ce qui est très simple.

Cordialement,

PGZ

[danbo52]

Merci pgz,

J'ai déjà pensé à ce type d'algorithme.
Mais comme je travaille uniquement avec des 0 et des 1, mon problème est d'afficher chaque matrice (à la demande).

Avec des valeurs de type 123, on obtient ce que tu présentes.

Le problème, c'est lorsqu'il va s'agir de traiter des matrices supérieures à 9, les chiffres sont mettre la pagaille.
Travailler en alphanumérique me limite à 26 caractères différents.

En revanche, en s'appuyant sur des matrices, il m'est permis de traiter de grandes matrices de dimensions supérieures à 9 ou à 26 si on travaille en alphanumérique.

Tout cela me pousse à travailler sur elle et ses 0 et 1, et non directement sur les valeurs 123, ABC, etc... et cela me donne une bien plus grande amplitude dans la taille des matrices.

Je planche sur ça et je reviens (pas de suite) si une ébauche de solution se met en mouvement.

Merci

[pgz]

Hello!

Le problème, c'est lorsqu'il va s'agir de traiter des matrices supérieures à 9, les chiffres sont mettre la pagaille.
Travailler en alphanumérique me limite à 26 caractères différents.

En revanche, en s'appuyant sur des matrices, il m'est permis de traiter de grandes matrices de dimensions supérieures à 9 ou à 26 si on travaille en alphanumérique.

C'est juste! Mais je te rappelle que si tu travailles avec n > 9, tu vas avoir un nombre de matrices effrayant :
10! = 3 628 800
13! = 6 227 020 800

Alors, au-delà de 26 c'est géant!

Dansle principe et pour traiter n> 9, on peut faire avec des collections (par exemple). Voici un code complet, mais avec n> 10, on va au dépassement de capacité.

Brut de fonderie :

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
Option Explicit
 
Dim oRng As Excel.Range
Dim lRang As Long
Dim v0 As Variant, vx As Variant
 
Sub test()
Call subMatrices(4)
End Sub
 
Sub subMatrices(ByVal n As Integer)
Dim col1 As VBA.Collection, col2 As VBA.Collection
Dim i As Integer, j As Integer
 
Set col1 = New VBA.Collection
Set col2 = New VBA.Collection
 
For i = 1 To n
    col1.Add i, CStr(i)
Next i
 
With ThisWorkbook.Worksheets(1)
    .UsedRange.ClearContents
    Set oRng = .Range(.Cells(1, 1), .Cells(n, n))
End With
lRang = 0
v0 = oRng.Value
 
For i = 1 To UBound(v0, 1)
    For j = 1 To UBound(v0, 2)
        v0(i, j) = 0
    Next j
Next i
 
Call subRecursive(col1, col2, n)
 
oRng.Columns.AutoFit
 
Set oRng = Nothing
Set col1 = Nothing
Set col2 = Nothing
 
End Sub
 
Sub subRecursive(ByVal col1 As VBA.Collection, ByVal col2 As VBA.Collection, ByVal n As Integer)
Dim i As Integer, j As Integer, col3 As VBA.Collection, col4 As VBA.Collection, s As String, nb1 As Integer, v As Variant
 
Set col3 = New VBA.Collection
Set col4 = New VBA.Collection
 
For i = 1 To col1.Count
    col3.Add col1.Item(i)
Next i
For i = 1 To col2.Count
    col4.Add col2.Item(i)
Next i
 
If col1.Count = 1 Then
    col2.Add col1(1), CStr(col2.Count + 1)
    vx = v0
    For i = 1 To col2.Count
        vx(i, col2(i)) = 1
    Next i
    oRng.Offset(lRang * (n + 1), 0).Value = vx
    lRang = lRang + 1
 
Else
    nb1 = col1.Count
    For i = 1 To nb1
 
        For j = col1.Count To 1 Step -1
            col1.Remove j
        Next j
        For j = 1 To col3.Count
            col1.Add col3.Item(j)
        Next j
 
        For j = col2.Count To 1 Step -1
            col2.Remove j
        Next j
        For j = 1 To col4.Count
            col2.Add col4.Item(j)
        Next j
 
        col2.Add col1.Item(i), CStr(col2.Count + 1)
        col1.Remove i
        Call subRecursive(col1, col2, n)
    Next i
End If
 
Set col3 = Nothing
Set col4 = Nothing
 
End Sub

J'ai testé n = 6. Je mets les matrices les unes au-dessus des autres (avec 1 ligne entre deux matrices) et on atteint déjà la ligne 5039, alors que 6! = 720. Je n'envisage même pas d'essayer n=9.

Cordialement,

PGZ

[danbo52]

pgz, merci pour ton bon mot.

J'ai effectivement, il y a quelques années, étudié les développements des factorielles élevées, mais dans mon cas, je me baserai au préalable sur un plan d'expérience qui va me proposer certaines conditions, conditions qui me feront éliminer (en fait c'est le code qui prendra la décision) une TRES GRANDE PARTIE des matrices, avant le lancement, afin de ne calculer qu'avec quelques rares grandes matrices.
Je traiterai des ensembles homogènes pour les intégrer dans un groupe. Au plan mathématique, je ferai de la "réduction" (une sorte d'homotétie), afin de simplifier la taille des matrices.

Elles pourront être grandes, mais rares.

Je viens de trouver le comment VBA du développement. Je testerai et reviendrai dire ce qu'il en est.
Merci pour les idées...