Algorithme de de combinaison

Question

slt à vous
 je développe en ce moment une application et j'aimerais avoir un programme java (optimal) qui prend en entrée une matrice de dimension n( n etant un paramètre) et retourne toutes les facons possibles de choisir une case par ligne.
vous avez bien compris qu'il s'agit d'un problème de permutation et qui deviens lent avec la taille de la matrice
plus tard il s'agit de coler des heuristiques
je vous remercie d'avance.

cs_DARKSIDIOUS · Answer

Bah je vois pas vraiment quel algo pourrait être plus optimal qu'un algorithme gloutant (faisant les permutations une à une de ta matrice) puisque de toute façon, il y aura n^(n-1)^(n-2)^...^2 combinaisons possibles !
Bon c'est sûr que pour un n au dessus de 4, ca va faire long, mais vu le nombre de possibilité, c'est normal !

Fonction récursive par contre quasi-obligatoire si tu veux traîter des matrices de grandeurs inconnue.

Sinon, quel est le but de cet algorithme ? Selon les cas d'utilisation, peut-être qu'il existe une méthode qui se passerait de l'énumération de toutes les matrices possibles...

super_toinou · Answer

darksidiou a raison, t es sur un pb a complexité exponnentielle, pour n assez grand tu pourra aller faire un foot le temps de trouver la réponse !!
Si tu veux coller des heuristiques dessus dans ce cas tu pourra squizzer un bon nombre de permutations possibles mais dans ce cas ton algo doit prendre cela en compte de suite sinon tu calculera toutes les solutions possibles dès le début et ensuite tu fera un filtre (ce qui n a pas gd interet)
j espere bien avoir comprit ton pb !
++ Toinou

cs_henrypower · Answer

slt à vous  DARKSIDIOUS et Toinou 
vous avez parfaitement raison. je sais que c'est un probleme de complexité exponentiel. j'ai essayez d'y rattacher des heuristiques mais j'ai pas pu trouver la bonne vu que je souhaite gérer les matrices de tailles quelconques. Pour etre plus clair mon problème est le suivant:
je dispose d'un matrice de dimension n*n  et où chaque ligne et colonne contient aumoins un symbole "zéro". je cherche un algorithme  donnant toutes les facons de former les n-uplets constitués des cordonnées(i et  j; 1<=i,j<=n) des cases  vérifiant les contraintes ci après:
- chaque case contient zéro
-  dans un n-uplet aucun i, ni j ne se repète.
J'espere que vous me proposerez un code java pour mon problème.
merci d'avance

super_toinou · Answer

fais des recherches sur les algo de matrices creuses, tu pourra certainement trouver des choses qui t aideront !!
++ Toinou

Algorithme de de combinaison

4 réponses

Votre réponse

Discussions similaires