Combinaison

Signaler
Messages postés
1
Date d'inscription
mercredi 11 avril 2007
Statut
Membre
Dernière intervention
11 avril 2007
-
Messages postés
3833
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
11 juin 2021
-
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.

1 réponse

Messages postés
3833
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
11 juin 2021
124
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.