Discussion :

[Willhelm]

Bonjour,
Je souhaite obtenir des matrices me donnant toutes les combinaisons possibles des éléments d'un vecteurs constitué de 1 et de 0, et sans répétition.
Il y a bien la fonction perms qui donne ce genre de chose.
Par exemple :

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
 
M = perms([1 1 0 0])
 
M =
 
     0     0     1     1
     0     0     1     1
     0     1     0     1
     0     1     1     0
     0     1     1     0
     0     1     0     1
     0     0     1     1
     0     0     1     1
     0     1     0     1
     0     1     1     0
     0     1     1     0
     0     1     0     1
     1     0     0     1
     1     0     1     0
     1     0     0     1
     1     0     1     0
     1     1     0     0
     1     1     0     0
     1     0     1     0
     1     0     0     1
     1     1     0     0
     1     1     0     0
     1     0     1     0
     1     0     0     1

Dans ce cas, je souhaiterais obtenir :

Code :

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

1
2
3
4
5
6
7
8
9
 
M =
 
     0     0     1     1
     0     1     0     1
     0     1     1     0
     1     0     0     1
     1     0     1     0
     1     1     0     0

Si quelqu'un a une solution ou connaît l'existence d'une fonction donnant ce résultat, ceci pourrait éviter une lourde programmation.
Merci

[duf42]

Bonjour,

Code :

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

1
2
 
M = unique(perms([1 1 0 0]), 'rows')

Bonne journée,
Duf

[Willhelm]

Super !
Merci beaucoup

Je viens d'avoir une idée, c'est du bricolage... en faisant :

Code :

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

1
2
3
4
 
M = perms([0 0 1 1]);
M = sortrows(M,1:4);
M = M(1:4:end,:);

Mais ton code est très efficace et beaucoup plus rapide !

[Willhelm]

En fait, les deux méthodes passent par la fonction perms qui construit une très grande matrice avant de la simplifier. Matlab est vite débordé !
L'idéal serait d'obtenir directement la matrice sans les lignes identiques... Avec une fonction récursive peut-être... Je vais chercher de mon côté, si quelqu'un est intéressé par une solution je posterai mes résultats.

[Caro-Line]

Quelqu'un y a déjà pensé avant toi :
MATLAB Central - File detail - uniqueperms

Vu l'auteur, je pense qu'on peut lui faire confiance pour que le code soit ultra-optimisé

[Willhelm]

Oui, effectivement je pense qu'il est difficile de faire mieux !
Merci Caro-Line

[Jerome Briot]

En fait, si je ne trompe pas, le code de John D'Errico est optimisé au sens de la quantité de mémoire utilisée...

La solution de duf42 utilise la fonction PERMS, donc toutes les permutations sont générées avant de n'en conserver que quelques unes. Alors que dans l'autre solution, seule les permutations utiles sont générées.

C'est ce que mentionne Bill McKeeman dans son commentaire en bas de page :

This clever code does part of what my more general perms does, but does it much more efficiently. Example:
(mine) perms('abracadabra', 'unique') generates 39916800 vectors, then sorts them and throws away the duplicates.
uniqueperms('abracadabra') generates 83160 vectors directly.

[Willhelm]

Oui, exactement.
Avec en passant par la fonction PERMS, l'ordinateur est vite "Out of memory" ! Ce qui limite les expériences que l'on souhaite réaliser.
La solution de John d'Ericco est efficace et très rapide.