Toutes les combinaisons gagnantes ...

Question

Bonjour &#224; tous,

Ca faisait longtemps que je ne vous avais pas mis &#224; contribution, alors je reviens. Mais l&#224;, c'est pas du fastoche fastoche ...

J'ai besoin, pour un calcul d'optimisation, de tester tous les cas possibles.

Entrons dans le concret :

Imaginons une petite fonction bien sympa, &#224; laquelle je donne en param&#232;tre un tableau d'entiers, et qui me retourne, un tableau de tableau d'entiers correspondant &#224; toutes les s&#233;ries faisables avec ces nombres ... Tableau de retour de taille factorielle par rapport &#224; la longueur du tableau en entr&#233;e.

C'est pas clair ??? Exemples :

{1, 2, 3} me retourne {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}
{1, 2, 3, 4} me retourne {{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4} ... }

Y'a-t-il un g&#233;nie dans le forum qui ai d&#233;j&#224; pondu un truc superpuissant tel que &#231;a ???

Nikoui · Answer

Les joies (et la puissance) des fonctions récursives : ///

/// Calcul les permutation d'une liste d'entier ///

/// Liste d'entier /// Liste de liste d'entier (une liste par permutation) private int[][] Permut(int[] source) { int[][] res; if (source.Length == 1) { res = new int[1][]; res[0] = new int[1]; res[0][0] = source[0]; return (res); } int nbPermut = Factoriel(source.Length); res = new int[nbPermut][]; int l; for (l = 0; l < nbPermut; l++) { res[l] = new int[source.Length]; } l = 0; for (int i = 0; i < source.Length; i++) { int[] subSource = new int[source.Length - 1]; int k = 0; for (int j = 0; j < source.Length; j++) { if (j != i) { subSource[k] = source[j]; k++; } } int[][] subRes = Permut(subSource); for (int m = 0; m < subRes.Length; m++) { res[l][0] = source[i]; for (int n = 0; n < subRes[m].Length; n++) { res[l][1 + n] = subRes[m][n]; } l++; } } return (res); } ///

/// Calcul la factorielle d'un entier ///

/// n /// Factoriel n private int Factoriel(int n) { if (n == 1) { return (n); } return (Factoriel(n - 1) * n); }

Nikoui · Answer

(Heu... si vous voulez la version "comment&#233;e" demandez moi, la c'est un peu cod&#233; "a l'arrache")

Nikoui · Answer

Voila avec un peu plus d'explication, ca sera plus exploitable comme ça : ///

/// Calcul les permutation d'une liste d'entier ///

/// Liste d'entier /// Liste de liste d'entier (une liste par permutation) private int[][] Permut( int[] source) { // Tableau de sortie int[][] res; if (source.Length == 1) { // On arrive à une chaine d'un seul caractère // Fin des appels récursif, on déboucle... res = new int[1][]; res[0] = new int[1]; res[0][0] = source[0]; return (res); } // Le nombre de permutation = factoriel(nombre d'entier dans la liste) int nbPermut = Factoriel(source.Length); // Initialisation du tableau de sortie = une ligne par permutation res = new int[nbPermut][]; int l; // Initialisation du contenu du tableau de sortie, chaque ligne fait la même taille // que la liste d'entrée for (l = 0; l < nbPermut; l++) { res[l] = new int[source.Length]; } l = 0; // Pour chaque élément de la liste source for ( int i = 0; i < source.Length; i++) { int[] subSource = new int[source.Length - 1]; int k = 0; // Création d'une sous liste en retirant l'élément en cours de la liste d'origine for ( int j = 0; j < source.Length; j++) { if (j != i) { subSource[k] = source[j]; k++; } else { // On n'ajoute pas l'élément en cours à la sous liste } } // On récupère toute les permutations pour cette sous liste int[][] subRes = Permut(subSource); // Pour chaque permutation de la sous liste, on ajoute une solution sous la forme : // [element_encours][x][x][x][x][x], avec [x][x][x][x][x] une des permutations de la sous liste for ( int m = 0; m < subRes.Length; m++) { // Element en cours res[l][0] = source[i]; // Recopie de la permutation n for ( int n = 0; n < subRes[m].Length; n++) { res[l][1 + n] = subRes[m][n]; } l++; } } return (res); } ///

/// Calcul la factorielle d'un entier ///

/// n /// Factoriel n private int Factoriel( int n) { if (n == 1) { // On arrive a la dernière multiplication // Fin des appels récursif, on déboucle... return (n); } return (Factoriel(n - 1) * n); }

maqfab · Answer

Merci pour cette r&#233;ponse qui m'a l'air correcte. J'ai trouv&#233; mon bonheur entre temps sur MSDN.com
Je note l'url ci dessous pour ceux qui cause anglais.
Merci tout de m&#234;me.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/permutations.asp

Toutes les combinaisons gagnantes ...

4 réponses

Votre réponse

Discussions similaires