Un problème de combinatoire

Bonjour,

Pour un projet de R.O. (Recherche opérationnelle) Statistique, je dois faire plusieurs choses:

1. Tout d'abord, lister l'ensemble A toutes les combinaisons de k éléments dans un ensemble de n éléments (k<=n)
2. Ensuite, pour chaque combinaisons Ai lister l'ensemble Bi toutes les permutations de j valeurs possibles.
3. Enfin pour chaque Bil vérifier si elles correspond aux contraintes (à définir en fonction de la recherche).

D'un point de vue mathématiques, l'ensemble A contient n! / ( k! ( n - k ) ! ) et chaque ensemble Bi contient j! éléments; soit un total de j! ( n! / ( k! ( n - k ) ! )).

Exemple:
Un bus de 80 places possède 15 passagers et chaque passager à une particularité spécifique parmi 10 catégories, recenser l'ensemble des possibilités de placement de ces passagers dans le bus.
Le nombre de combinaisons total est donc de 10! ( 80! / ( 15! (80 - 15) ! )) = 5 472 782 816 133 670 000 000

Je voudrais votre avis sur comment procéder, dois-je commencer par calculer l'ensemble A dans son intégralité ou faire en sorte qu'au fur et à mesure que celui-ci se remplit créer les ensembles Bi auxquels j'ai "accès"; ou aborder une toute autre approche..?

De plus j'aimerais un coup de main sur quelques points où je ne vois pas comment procéder:

* Gérer la sauvegarde du processus, de sorte à pouvoir le reprendre ultérieurement au stade où il s'était arrêté (comme pour le moment je gère tout cela à l'aide de récursive je n'arrive pas à correctement sauver mon état)
* Permettre l'affichage de la progression à l'aide d'un ProgressBar, le problème étant les grands nombres à gérer et quel format utiliser pour les stocker sachant que cela doit ralentir le moins possible le reste (donc les Decimal à éviter par exemple)
* Toute piste utile à l'optimisation du tout aussi bien en terme de vitesse d'exécution, qu'en terme de mémoire (du processus en lui même d'une part et du format de stockage des résultats valides d'autre part, sachant que toute base de données est exclue (au moins pour le moment))


Merci d'avance à tous, pour l'attention portée à ce message ainsi qu'à toute aide apportée !

Bonjour,
Toutes mes condoléances, j'ai pas un souvenir impérissable de mes cours de R.O. :mouarf:

Pour ton deuxième point, je te conseille de passer par la backgroundworker qui gère un thread séparé (tu trouveras sans pb des tutos à ce sujet).
Avantages : ton appli n'est pas bloquée et cette classe gère l'avancement de l'algo.

Tu peux ajouter à la form affichant le progressbar un bouton pause/resume qui va (par exemple) enregistrer dans un fichier les valeurs en cours des paramètres de ta fonction récursive.
Une fonction de chargement des valeurs sauvegardées qui appelle ton traitement en alimentant les paramètres avec ces valeurs et ça devrait faire l'affaire !

Pour les backgroundworkers je m'en sert déjà de deux (un pour les combinaisons) et un pour les permutations de chacune en fonction des valeurs admissibles.

En ce qui concerne ta méthode de sauvegarde elle ne conviendra pas, car je dois non seulement enregistrer l'état des valeurs mais aussi les niveaux d'empilage de la fonction récursive c'est surtout ce point qui me pose problème.

Tu peux très bien ajouter en paramètre ce niveau d'empilage (qui est mis à jour dans la fonction récursive) !

En tout cas, si tu dois parcourir la totalité des combinaisons possible, je ne suis pas sur que tu n'atteignes pas des limites en terme de mémoire et de temps de traitement. N'y a t'il pas des règles d'éliminations (des non sens) qui réduiraient la combinatoire ?

Enregistrer la profondeur de la récursive ne suffira malheureusement pas, quant à réduire les possibilités cela ne pourra se faire de toute façon qu'après le listage des possibilités, car le seul moment où l'on peut restreindre le choix, c'est lors des choix des permutations, mais les combinaisons elles doivent etre recensée de façon exhaustive