Discussion :

[Opsse]

Bonjour,

Mon titre n'est peut être pas très claire, mais je ne sais justement pas comment nommer cette méthode (c'est peut être pour cela que google de m'aide pas). Donc je m'explique.

Je veux tester toutes les combinaisons d'une série mais en utilisant qu'une seule fois chaque élément par combinaison.
Un petit exemple, avec la série : a b c
Je cherche un algo qui me sorte :

abc
acb
bac
bca
cab
cba

En bonus j'aimerais pourvoir choisir la taille de la combinaison, toutes les combinaisons de 1 élément, puis de 2, puis de 3 ...
Il s'est avéré que ce n'est pas si facile que je l'avais pensé et bien que j'aurais aimé le trouver par moi même, je ne suis pas arrivé à grand chose de concluant.

Si vous avez des pistes, ou des noms d'algos déjà existants je suis fortement intéressé !

[ToTo13]

C'est comme tu le dis dans le titre une méthode de recherche brute, tu trouveras ton bonheur en tapant "recherche exhaustive".
Disons que tu as un tableau T d'éléments dont tu veux toutes les combinaisons

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Solution S
 
Fonction F(T, int deep)
Si deep supérieur à la longueur de T
	Afficher la solution.
	Sortir de la fonction.
 
Pour tous les élements de T
	Si T[deep] n'est pas déjà utilisé dans la solution
		Solution[deep] = T[i]
		F(T, deep+1)
fin fonction

[Opsse]

Je ne suis pas sur de bien comprendre l'algo que tu proposes, notamment la ligne "Si T[deep] n'est pas déjà utilisé dans la solution", ce ne serait pas "Si T[i] n'est pas déjà utilisé dans Solution[deep]" ?
Et "Solution[deep] = T[i]" tu veux bien dire d'ajouter T[i] à la suite ? Pas d'écraser la valeur de Solution[deep] ?


En tout cas la récursivité m'a donné des idées.
Avec T1 la liste d'éléments et T2 une liste initialement vide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fonction F(List T1, List T2)
 
	Pour tout les éléments E de T1
 
		T2 ajouter E
		T1 retirer E
 
		Si T2 est la solution
 
			Afficher T2
 
 
		F(T1, T2)
 
fin fonction

Ce qui devrait, si tout fonctionne comme je le pense, tester toutes les solutions possibles et afficher celles qui correspondent à mes critères. Pour optimiser l'algo j'aimerais parcourir les combinaisons de la plus courte à la plus longue et stopper la recherche dès la 1er solution trouvé (la plus courte donc). Le problème est que je les parcours dans une ordre un peu anarchique (a - ab - abc - ac - acb - b - ...).

Que pensez vous de cet algo ? Est il bon ? Des idées pour l'optimiser ?

[ToTo13]

la ligne "Si T[deep] n'est pas déjà utilisé dans la solution", ce ne serait pas "Si T[i] n'est pas déjà utilisé dans Solution[deep]" ?

Oui !

Et "Solution[deep] = T[i]" tu veux bien dire d'ajouter T[i] à la suite ? Pas d'écraser la valeur de Solution[deep] ?

Si, tu écrases, sinon tu accumules toutes les solutions testées.