Algorithme pour générer des matrices

Version imprimable

12/12/2007, 16h54
senacle

Algorithme pour générer des matrices

J'ai une matrice (i,j) dont certains éléments valent 0.

Je souhaite générer toutes les matrices qui ont un seul élément non nul dans chaque colonne.

Exemple :

[[11,0],[21,12]]

Je veux obtenir :

[[11,0],[0,12]]

[[0,0],[21,12]]

J'essaie de mettre en forme des boucles imbriquées, mais je coince.

Une idée ?
12/12/2007, 19h13
PRomu@ld

Montre nous ce que tu as fais, on pourra peut-être t'aider.
12/12/2007, 22h31
Zavonen

Tu parcoures tes colonnes une à une.
Tu cherches d'abord si une colonne comporte 2 zéros ou plus.
Dans ce cas, c'est foutu, on arrête tout.
Si c'est OK on recommence.
Deux cas peuvent se produire:
Soit il y a un zéro exactement, alors rien à faire, on garde la colonne telle quelle, et on passe à la suivante dans laquelle on déplace le zéro sur toutes les positions possibles, générant ainsi de nouvelles colonnes donc de nouvelles matrices.
Je vais essayer de rédiger ça.

C'est tout ce que j'ai trouvé, un truc récursif. Il doit y avoir mieux:

Code:

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
#!/usr/bin/env python
 
# on travaille sur les lignes au lieu des colonnes
# ilsuffit de transposer
from copy import *
 
# L représente une ligne (colonne)
def nombre_de_zeros(L):
    n=0
    for i in L:
        if i==0:
            n=n+1
    return n
 
#remplace le terme de rang i par 0
def substitue(L,i):
    L[i]=0;
    return L
 
 
# génère un ensemble de lignes correspondant au nombre de zéros
# si ce nombre est <2
def expand (L):
    E=[]
    if nombre_de_zeros(L)==1:
        E.append(L) # une seule possibilité
    else:
        for i in range(0,len(L)):
            E.append(substitue(copy(L),i)) #autant de possibilités que d'éléments dans la ligne
    return E
 
# travail préparatoire
# générer pour chaque ligne les possibilité
# et tout rassmbler dans une liste de listes
def pregenerate (M):
    S=[]
    for L in M:
        if nombre_de_zeros(L)>1:
            return S   # c'est fini
        else:
            S.append(expand(L))
    return S
 
#utilitaire pour la fonction récursive generate
def combine (H,T):
    R=[]
    for M in H:
        for L in T:
            K=[]
            K.append(M)
            for i in L:
                K.append(i)
            R.append(K)
    return R
 
# fonction récursive prenant en argument le résultat de pregenerate
def generate (S):
    if len(S)==1:
        return S
    else:
        H=S.pop(0)
        return combine(H,generate(S))
    return
 
# la fonctions qui donne toutes les possiblités
def solutions(matrice):
    return generate(pregenerate(matrice))
 
def main():
    print solutions([[1,2,3],[4,5,6],[7,9,0]])
 
if __name__ == '__main__':
    main()

13/12/2007, 09h33
senacle

En python...Super, c'est ce langage que j'utilise.

Je viens de faire un essai, mais le résultat n'est pas ce qu'il me faut. Bravo quand même pour le travail.

Je prends un autre exemple.

Matrice de départ :

[1,2,3]
[0,4,5]
[6,7,0]

Les combinaisons possibles :

[1,2,3]
[0,0,0]
[0,0,0]

[1,2,0]
[0,0,5]
[0,0,0]

[1,0,3]
[0,4,0]
[0,0,0]

[1,0,0]
[0,4,5]
[0,0,0]
....

En fait, il faut des matrices avec un seul élément non nul sur chaque colonne.

J'ai pensé à ça :

Je prends chaque colonne de la matrice initiale.
Pour chacune de ces colonnes, je génère les combinaisons avec un seul élément non nul.
Enfin, je combine les combinaisons...

Un exemple est plus clair.

Matrice de départ :

[1,2,3]
[0,4,5]
[6,7,0]

Combinaison pour chaque colonne :

Colonne 1
[1]
[0]
[0]

[0]
[0]
[6]

Colonne 2
[2]
[0]
[0]

[0]
[4]
[0]

[0]
[0]
[7]

Colonne 3
[3]
[0]
[0]

[0]
[5]
[0]

Combinaison 1 de la colonne 1 + combinaison 1 de la colonne2 + combinaison 1 de le colonne 3 :

[1][2][3]
[0][0][0]
[0][0][0]

Combinaison 1 de la colonne 1 + combinaison 1 de la colonne2 + combinaison 2 de le colonne 3 :

[1][2][0]
[0][0][5]
[0][0][0]

C'est peut-être un peu trop "systématique", mais ça a l'air de fonctionner.

Il me semble aussi que ce serait plus facile de manipuler les lignes plutôt que les colonnes pour faire les combinaisons de combinaisons (là, c'est une question de langage de programmation).
Du coup, on transpose la matrice de départ, on fait les combinaisons sur les lignes, et on transpose la matrice générée.

Qu'en pensez-vous ?

Autant pour moi, j'avais compris seul un élément nul.
Il y a juste un changement cosmétique à faire.
essaie cette version

Code:

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
#!/usr/bin/env python
 
# on travaille sur les lignes au lieu des colonnes
# ilsuffit de transposer
from copy import *
 
# L représente une ligne (colonne)
def nombre_de_nonnuls(L):
    n=0
    for i in L:
        if i!=0:
            n=n+1
    return n
 
#remplace tous les termes par 0 sauf celui de rang i
def substitue(L,i):
    for j in range(0,len(L)):
        if j!=i:
            L[j]=0;
    return L
 
 
# génère un ensemble de lignes correspondant aux éléments non nuls de L
def expand (L):
    E=[]
    for i in range(0,len(L)):
        if L[i]!=0:
            E.append(substitue(copy(L),i)) # une seule possibilité
    return E
 
# travail préparatoire
# générer pour chaque ligne les possibilité
# et tout rassmbler dans une liste de listes
def pregenerate (M):
    S=[]
    for L in M:
        S.append(expand(L))
    return S
 
#utilitaire pour la fonction récursive generate
def combine (H,T):
    R=[]
    for M in H:
        for L in T:
            K=[]
            K.append(M)
            for i in L:
                K.append(i)
            R.append(K)
    return R
 
# fonction récursive prenant en argument le résultat de pregenerate
def generate (S):
    if len(S)==1:
        return S
    else:
        H=S.pop(0)
        return combine(H,generate(S))
    return
 
# la fonctions qui donne toutes les possiblités
def solutions(matrice):
    return generate(pregenerate(matrice))
 
def main():
    print solutions([[1,2,3],[0,4,5],[6,7,0]])
 
if __name__ == '__main__':
    main()

13/12/2007, 11h02
senacle

C'est presque ça....
Le résultat donne 6 matrices de 4 lignes et 3 colonnes, alors que ça doit être 12 matrices de 3 lignes et 3 colonnes.

J'avais pas bien lu, mais je vois qu'effectivement, c'est plus simple de travailler sur les lignes plutôt que sur les colonnes.
En relisant encore, je m'aperçois que ce que j'explique, et bien c'est exactement ce que tu fais....

Bon, d'accord, j'aurais dû lire plus attentivement:oops:

C'est la sortie de la récursion qui était mauvaise
Nouvelle tentative:

Code:

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
#!/usr/bin/env python
 
# on travaille sur les lignes au lieu des colonnes
# ilsuffit de transposer
from copy import *
 
#remplace tous les termes par 0 sauf celui de rang i
def substitue(L,i):
    for j in range(0,len(L)):
        if j!=i:
            L[j]=0;
    return L
 
 
# génère un ensemble de lignes correspondant aux éléments non nuls de L
def expand (L):
    E=[]
    for i in range(0,len(L)):
        if L[i]!=0:
            E.append(substitue(copy(L),i)) # une seule possibilité
    return E
 
# travail préparatoire
# générer pour chaque ligne les possibilité
# et tout rassmbler dans une liste de listes
def pregenerate (M):
    S=[]
    for L in M:
        S.append(expand(L))
    return S
 
#utilitaire pour la fonction récursive generate
def combine (H,T):
    R=[]
    for M in H:
        for L in T:
            K=[]
            K.append(M)
            for i in L:
                K.append(i)
            R.append(K)
    return R
 
def split(L):
    R=[]
    H=L[0]
    for X in H:
        R.append([X])
    return R
 
# fonction récursive prenant en argument le résultat de pregenerate
def generate (S):
    if len(S)==1:
        return split(S)
    else:
        H=S.pop(0)
        return combine(H,generate(S))
    return
 
# la fonctions qui donne toutes les possiblités
def solutions(matrice):
    return generate(pregenerate(matrice))
 
def main():
    print solutions([[1,2,3],[0,4,5],[6,7,0]])
 
if __name__ == '__main__':
    main()

Super !

J'ai ajouté la fonction de transposition.

Voici ce que ça donne au final :

Code:

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
 
#!/usr/bin/env python
 
# on travaille sur les lignes au lieu des colonnes
# ilsuffit de transposer
from copy import *
 
def transposition(L) :
	l = len(L)
	c = len(L[0])
	T = [0]*c
	for i in range(c) :
		T[i] = [0] * l
	for i in range(c) :
		for j in range(l) :
			T[i][j] = L[j][i]
	return T
 
#remplace tous les termes par 0 sauf celui de rang i
def substitue(L,i):
    for j in range(0,len(L)):
        if j!=i:
            L[j]=0;
    return L
 
 
# génère un ensemble de lignes correspondant aux éléments non nuls de L
def expand (L):
    E=[]
    for i in range(0,len(L)):
        if L[i]!=0:
            E.append(substitue(copy(L),i)) # une seule possibilité
    return E
 
# travail préparatoire
# générer pour chaque ligne les possibilité
# et tout rassmbler dans une liste de listes
def pregenerate (M):
    S=[]
    for L in M:
        S.append(expand(L))
    return S
 
#utilitaire pour la fonction récursive generate
def combine (H,T):
    R=[]
    for M in H:
        for L in T:
            K=[]
            K.append(M)
            for i in L:
                K.append(i)
            R.append(K)
    return R
 
def split(L):
    R=[]
    H=L[0]
    for X in H:
        R.append([X])
    return R
 
# fonction récursive prenant en argument le résultat de pregenerate
def generate (S):
    if len(S)==1:
        return split(S)
    else:
        H=S.pop(0)
        return combine(H,generate(S))
 
# la fonctions qui donne toutes les possiblités
def solutions(matrice):
	C =	generate(pregenerate(transposition(matrice)))
	for i in range(len(C)) :
		C[i] = transposition(C[i])
	return C
 
def main():
    print solutions([[1,2,3],[0,4,5],[6,7,0]])
 
if __name__ == '__main__':
    main()

J'ai trouvé ça pour faire la transposition : http://numpy.scipy.org//
Mais j'ai préféré écrire ma fonction, c'est moins lourd que de récupérer toute la bibliothèque.

:merci: et :ave::bravo: