«
»
Combinaisons

Combinaisons

Quand arrive le temps d’un test qui doit utiliser des combinaisons d’une chaîne de caractères / de divers éléments, un programmeur est confronté à faire un algorithme pas toujours évident.

Ci-dessous, deux exemples de code. Le premier permet de trouver toutes les combinaisons d’un nombre de caractères défini parmi ceux d’une chaîne initiale, le second les combinaisons d’éléments divers.

Attention, le terme « combinaison » n’est pas celui décrit en mathématique puisque les résultats ci-dessous montrent que le résultat comprend aussi ceux contenant moins d’éléments que demandés (ex : on demande dans l’exemple 1, 3 caractères, mais des résultats en 1 et 2 caractères sont donnés). Qui peut le plus peut le moins … si ces premiers résultats ne vous sont pas utiles, il suffira de mettre (pour l’exemple 1) : soit SI nTailleItem=3 ALORS tabRes.Ajoute(sItem) soit sChaineDébut = « AAA »

Exemple 1

Cette fonction vient avec quelques paramètres intéressants : chaîne du début (où on commence), chaîne de fin (où on s’arrête) et personnalisation des caractères à utiliser.

Par exemple, avec un nbr de caractères de 3 utilisant la chaîne « ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 », cela donne :
A
B
C
…
9
AA
AB
…
99
AAA
AAB
…
999

tabRésultat est un tableau de chaînes = CombinaisonCaractères(3)
fSauveTexte("C:\temp\code.txt",TableauVersChaîne(tabRésultat,RC))
Info("fini")
PROCÉDURE CombinaisonCaractères(LOCAL nNombreCaractèresMax est un entier,sChaineDébut est une chaîne="",LOCAL sChaineFin est une chaîne="",LOCAL sListeCaractères est une chaîne = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789") : tableau de chaîne
//abcdefghijklmnopqrstuvwxyz"	//àèìòùâêîôûäëïöü@ç=+_-()*&?%$/!|\#£¢¤¬¦²³¼½¾{}<>«»°,'.É[]"
 
bTermine	est un booléen	= Faux			//pour terminer le traitement
sItem		est une chaîne
nTailleItem	est un entier
t			est un entier	= Taille(sListeCaractères)
tabRes		est un tableau de chaînes
 
//vérifications d'usage
SI sListeCaractères="" ALORS Erreur("La liste des caractères ne peut pas être vide");RENVOYER tabRes
SI sChaineDébut>"" _ET_ sChaineFin>"" _ET_ sChaineFin<sChaineDébut ALORS Erreur("La chaîne de fin est inférieure à la chaîne de début");RENVOYER tabRes SI sChaineDébut>"" ALORS
	SI Taille(sChaineDébut)>nNombreCaractèresMax ALORS Erreur("La taille de la chaîne de début dépasse le nombre de caractères maximum");RENVOYER tabRes
	//vérifier que les caractères sont dans sListeCaractères
	POUR c=1 _À_ Taille(sChaineDébut)
		SI Position(sListeCaractères,sChaineDébut[c])<1 ALORS Erreur(ChaîneConstruit("%1 de la chaîne de début n'est pas contenu dans la liste des caractères",sChaineDébut[c]));RENVOYER tabRes FIN sItem=sChaineDébut;tabRes.Ajoute(sItem) FIN SI sChaineFin>"" ALORS
	SI Taille(sChaineFin)>nNombreCaractèresMax ALORS Erreur("La taille de la chaîne de fin dépasse le nombre de caractères maximum");RENVOYER tabRes
	//vérifier que les caractères sont dans sListeCaractères
	POUR c=1 _À_ Taille(sChaineFin)
		SI Position(sListeCaractères,sChaineFin[c])<1 ALORS Erreur(ChaîneConstruit("%1 de la chaine de fin n'est pas contenu dans la liste des caractères",sChaineFin[c]));RENVOYER tabRes
	FIN
FIN
 
nTailleItem = Max(Taille(sChaineDébut),1)
 
nDernier	est un entier = Position(sListeCaractères,sItem[nTailleItem])
BOUCLE
	DernierChar(nDernier);nDernier=1
	SI bTermine _OU_ sItem=sChaineFin ALORS SORTIR SINON Multitâche(-1)
	SI AjoutePrécédent(nTailleItem) ALORS sItem[nTailleItem]=sListeCaractères[1];tabRes.Ajoute(sItem) SINON SORTIR
FIN
RENVOYER tabRes
 
PROCÉDURE INTERNE DernierChar(nDepuisLettre est un entier)
POUR c=nDepuisLettre+1 À t
	sItem[nTailleItem]=sListeCaractères[c]
	tabRes.Ajoute(sItem)
	SI bTermine _OU_ sItem=sChaineFin ALORS SORTIR
FIN
FIN
 
PROCÉDURE INTERNE AjoutePrécédent(LOCAL nPos est un entier) : booléen
SI sItem[nPos]=sListeCaractères[t] ALORS
	SI sItem=Répète(sListeCaractères[t],nTailleItem) ALORS
		SI nTailleItem<nNombreCaractèresMax ALORS nTailleItem++;sItem=Répète(sListeCaractères[1],nTailleItem) SINON RENVOYER Faux
	SINON
		SI PAS AjoutePrécédent(nPos-1) ALORS RENVOYER Faux
	FIN
SINON
	sItem=Gauche(sItem,nPos-1)+sListeCaractères[Position(sListeCaractères,sItem[nPos])+1]+Répète(sListeCaractères[1],nTailleItem-nPos)
FIN
RENVOYER Vrai
FIN

Exemple 2

Le résultat de l’exemple ci-dessous donnera (le séparateur fonctionne tant pour exploiter la chaîne de référence que pour séparer les éléments dans le tableau final) :
ABC
DEF
GHI
ABC,DEF
ABC,GHI
DEF,GHI
ABC,DEF,GHI

tabRésultat est un tableau de chaînes = Combinaison("ABC,DEF,GHI",",")
PROCÉDURE Combinaison(sRéférence est une chaîne,sSéparateur est une chaîne) : tableau de chaîne
tabRes,tabTemp,tabRéférence sont des tableaux de chaînes
sCombinaison	est une chaîne
 
ChaîneVersTableau(sRéférence,tabRéférence,sSéparateur)
tabRes = tabRéférence	//au moins une fois chaque élément de la référence
 
POUR nRéférence = 1 _À_ tabRéférence..Occurrence
	//prendre les éléments dans le résultat pour faire d'autres résultat en ajoutant, s'il n'existe pas, un élément de référence
	POUR nRésultat = 1 _À_ tabRes..Occurrence
		SI Position(tabRes[nRésultat],tabRéférence[nRéférence])<1 ALORS //pas de doublon d'élément
			sCombinaison=tabRes[nRésultat]+sSéparateur+tabRéférence[nRéférence]
			ChaîneVersTableau(sCombinaison,tabTemp,sSéparateur);TableauTrie(tabTemp);sCombinaison=TableauVersChaîne(tabTemp,sSéparateur)	//pas de doublon de combinaison
			SI TableauCherche(tabRes,tcLinéaire,sCombinaison)<1 ALORS TableauAjoute(tabRes,sCombinaison) 
		FIN
	FIN
FIN
 
RENVOYER tabRes