combinaison

Question

Salut à tous
e cherche un algorithme qui permet d'afficher les differentes combinaisons formées formées par un chaine de  N caractères. 
exemple pour Ch='1234' on aura 1234,1243,1342,1324,... etc. on tour en aura 24 combinaion soit N!
y-a-t'il quelqu'un qui peut m'aider ? 
et merci d'avance.

cptpingu · Answer

Est-ce que par hasard ce ne serais pas un exercice donné par un de tes professeurs, que tu essaierais de nous faire faire à ta place ? En tout cas ici on ne fournit pas de code, mais si tu fais voir ce que tu as déjà fait, on peux te corriger, et te dire ce qui ne vas pas dans ton code. Ca pourrait se faire à l'aide d'un graphe ou d'un "pseudo graphe" (du recursif en fait). On peut aussi le faire sous forme d'arbre général, mais pour de grande valeurs, tu risques de faire exploser la pile, ce qui ne se produira pas avec un graphe, ou avec une simple recursion. Je te propose une méthode itérative, avec une pile: npile = -1 i = 0 j = 0 res = 0 tant que (npile > -2) Si (npile n - 1 et i n) alors si ((!j ou res > liste[j-1]) et res != nb) liste[j] = res j = j+ 1 fin si fin si Si i < n alors Si (!m[i]) npile = npile + 1 pile[npile] = i res = res * 10 res = res + chiffre[i] m[i] = 1 i = 0 sinon i = i + 1 Fin Si Sinon Si (npile >= 0) i = pile[npile] pile[npile] = -1 npile-- m[i] = 0 i++ res = res / 10 sinon npile = -2 fin si Fin si avec "chiffre" ton tableau de depart et "liste" ta liste ou tu stocke toutes les possibilités. "m" représente ton tableau de marque Pour générer toutes les permutations, il faut stocker les chiffres du nombre dans un tableau, utiliser une pile et un tableau de marque. Dans la pile, on empile les indices des chiffres non marqués et on les marque. L'idée est de commencer par l'indice 0. Puis à chaque fois que l'on dépile un élément (on enlève la marque), le prochain indice que l'on peut empiler c'est indice + 1. Comme ça, on est sûr de ne pas réempiler indice! Pour envisager les permutations dans l'ordre croissant, il suffit de trier les chiffres dans l'ordre croissant dans le tableau de chiffres avant d'envisager toutes les permutations. Lorsqu'il y a des doublons, l'ordre croissant des permutations n'est plus respecté, donc dès qu'une permutation est <= à la permutation précédente, c'est un doublon! Bonne chance.

Combinaison

1 réponse

Votre réponse

Discussions similaires