Recherche de tous les tableaux uniques possibles dans une matrice

Question

Lorsqu'une matrice carrée est donnée, quelle serait la meilleure façon de trouver tous les tableaux possibles sans utiliser plus d'un élément de n'importe quelle rangée/colonne dans chaque matrice?

Par exemple, dans une matrice comme ceci:

0 2 3 
1 2 3 
1 2 0 

Il serait alors passer par là comme ceci:

Et puis il génèrerait la liste suivante des tableaux:

123 
123 
023 
123 
120 
020 

Answer 1

Vous pouvez mapper directement chaque tableau sur une permutation des chiffres (0 .. taille-1). Pour vous montrer comment cela fonctionne, la permutation (2,1,0) correspond aux 3 coordonnées (2,0), (1,1), (0,2). Les 6 exemples que vous avez données sont

(2,1,0) (1,2,0) (0,2,1) 

(2,0,1) (1,0,2) (0,1,2) 

Pour expliquer la cartographie, permet de prendre la première permutation (2,1,0) --> (2,0), (1,1), (0,2). Ensuite, les valeurs que vous voulez utiliser sont array[2][0], array[1][1], array[0][2]

Maintenant, la question est de savoir comment générer chaque permutation. Il y a quelques algorithmes, dont l'un est implémenté en Java ici: http://www.merriampark.com/perm.htm