Lister les combinaisons possibles...

Fermé

nicosob Messages postés 3 Date d'inscription vendredi 30 octobre 2015 Statut Membre Dernière intervention 30 octobre 2015 - 30 oct. 2015 à 09:04
Flachy Joe Messages postés 2103 Date d'inscription jeudi 16 septembre 2004 Statut Membre Dernière intervention 21 novembre 2023 - 31 oct. 2015 à 12:04

Bonjour,

Je vais aller directement dans le coeur de mon problème.
Je voudrais afficher une liste de combinaisons possibles.

Pour illustrer ma requête, je vais prendre un exemple concret : dans un hôtel, j'ai 3 chambres différentes : R1, R2 et R3. Chaque chambre peut contenir un nombre maximum de personnes. Ici, admettons que R1 peut accueillir 3 personnes maximum, R2 peut en accueillir 4 max et R3 peut en accueillir 15 max.
Je voudrais avoir un algorithme qui me permette de lister les combinaisons de chambre en fonction d'un nombre de personnes annoncés.
Dans mon exemple, si j'ai 10 personnes annoncées, les combinaisons que je veux sont :
1 x R3
3 x R2
2 x R2 + 1 x R1
1 x R2 + 2 x R1
4 x R1

Je cherche donc un algorithme qui aurait en entrée les données suivantes :
- nombre de personnes attendues
- Liste des chambres et de leur contenance max
et du coup en sortie :
- combinaisons des chambres pour faire rentrer tout ce petit monde !

Je me casse un peu les dents dessus... Toute aide serait appréciée ;)
Merci d'avance !

A voir également:

2 réponses

Réponse 1 / 2

Utilisateur anonyme
30 oct. 2015 à 09:48

Bonjour

selon le langage cible, la solution sera sensiblement différente.
Peux tu préciser ce langage?

nicosob Messages postés 3 Date d'inscription vendredi 30 octobre 2015 Statut Membre Dernière intervention 30 octobre 2015
30 oct. 2015 à 10:00

Bonjour,

Merci pour l'intérêt porté à ma question.
A priori, le code finale est en php, mais honnêtement, je suis preneur d'une solution algorithmique pure, ou même d'une solution sur Excel ! :)

Réponse 2 / 2

Flachy Joe Messages postés 2103 Date d'inscription jeudi 16 septembre 2004 Statut Membre Dernière intervention 21 novembre 2023 260
30 oct. 2015 à 12:41

La solution est un arbre, expl pour 10 clients et les chambre [R1:3, R2:4, R3:15] :
https://pix.toile-libre.org/upload/original/1446204851.jpg

A partir de la liste des places dans les chambres, on peut construire l'arbre de tous les remplissages possibles avec des imbrications de boucles ou une fonction récursive.
A partir de cet arbre, on coupe les branches qui contiennent plus de personnes placées que de places demandées et on obtient toutes les solutions pour un nombre donné.

nicosob Messages postés 3 Date d'inscription vendredi 30 octobre 2015 Statut Membre Dernière intervention 30 octobre 2015
30 oct. 2015 à 14:15

:) Merci beaucoup Joe !!
Le souci dans ton arbre c'est que chaque chambre n'est utilisée qu'une seule fois.
L'arbre n'est donc pas complet... Mais c'est une piste que je vais essayer de creuser.

Il me rend fou ce truc ! :D

Flachy Joe Messages postés 2103 Date d'inscription jeudi 16 septembre 2004 Statut Membre Dernière intervention 21 novembre 2023 260
31 oct. 2015 à 12:04

Ok, je viens de comprendre que R1, R2 et R3 sont des types de chambre.
Il suffit de faire une liste qui contient plusieurs occurrence de chaque type en entrée pour que ça revienne au même.
expl : 3 chambre R1, 4 R2 et 2 R3 donne une liste [ 3, 3, 3, 4, 4, 4, 4, 15, 15 ]

Mais ton arbre contiendra alors des branches équivalente du genre
(3 dans R1a , 2 dans R1b, 5 dans R3) = (2 dans R1a , 3 dans R1b, 5 dans R3)

Si tu ne cherche qu'avec des remplissages optimisés pour un max de personnes par chambre, ça devrait pouvoir se simplifier.

Discussions similaires

Toutes les combinaisons à 4 chiffres de 0000 a 9999

combinaisons à 3 CHIFFRES

SQL Lister les tables d'une base

combinaisons possibles de 0 à 9 par tranche de 3 chiffres

Combinaisons possibles avec 3 séries de 3 nombres