Combinaisons d'éléments avec maximum

[europeest]

Bonjour à tous

Nouveau sur le forum, je tente sans succès pour l'instant de resoudre le problème suivant (en pièce jointe)

J'ai une série de catégories (20 catégories) dont les valeurs peuvent être comprises entre 0 et 10. Le total des valeurs pour chaque combinaison potentielle est fixe et doit être égal à 71.

Je cherche à établir la liste de toutes les combinaisons potentielles sous la forme d'un tableau. J'ai essayé via divers IF etc..., RANDBETWEEN et autres, mais sans succès jusqu'à présent.

Avez-vous déjà résolu des questions similaires, quelle est l'approche à aborder?

Merci pour votre attention.
Cordialement

 

[CBernardT]

Re : Combinaisons d'éléments avec maximum

Bonjour europeest et le forum,

Bienvenue sur le forum

Une solution par VBA. Activer le bouton "TIRAGE".

Dans la configuration actuelle, le nombre de colonnes peu être augmenté mais pas celui des lignes du tableau.
Le total est également fixé dans la macro.

 

[europeest]

Re : Combinaisons d'éléments avec maximum

Merci pour votre réponse rapide Bernard, cela fonctionne bien pour les 32 premieres colomnes.

Peut-on savoir pour ce cas de figure combien y-a-t-il de combinaisons possibles ayant pour total 71 (dans cet exemple), et afficher tous les cas dans le tableau?
Dans le fichier, j'avais indiqué 32 cas de figures potentielles, mais il doit y en avoir beaucoup plus, non?
L'idée est de pouvoir afficher en colonnes toutes les combinaisons possibles compte tenu des données de base (nombre de lignes, min et max, somme des éléments dans la macro).

merci d'avance!

 

[KenDev]

Re : Combinaisons d'éléments avec maximum

Bonsoir europeest, CBernardT,

Peut-on savoir pour ce cas de figure combien y-a-t-il de combinaisons possibles ayant pour total 71 (dans cet exemple)

Oui, mais c'est long.

, et afficher tous les cas dans le tableau?

Non, y'en a trop.

Dans le fichier, j'avais indiqué 32 cas de figures potentielles, mais il doit y en avoir beaucoup plus, non?

Ca dépend. Si tu considères que 2346225261778251040 est beaucoup plus que 32 alors oui.

L'idée est de pouvoir afficher en colonnes toutes les combinaisons possibles compte tenu des données de base (nombre de lignes, min et max, somme des éléments dans la macro).

C'est une idée.

Deux subs, dans le classeur joint.

La sub schemas, celle va générer tous les schémas de combinaisons possibles (1 par ligne) sur 20 colonnes (239 457 lignes dans l'exemple). Un exemple de ce que j'appelle un schéma :
10 9 6 6 6 6 6 4 4 3 3 1 1 1 1 1 1 1 1 0
qui correspond à toutes les combinaisons ayant :
1 élément valant 10
1 élément valant 9
5 éléments valant 6
2 éléments valant 4
2 éléments valant 3
8 éléments valant 1
1 éléments valant 0

La sub NbComb qui va écrire à droite de chacune des lignes précédentes le nombre de combinaisons correspondant à ce schéma.

Il ne reste qu'a sommer cette colonne pour avoir le nombre de colonnes nécessaires à l'écriture de toutes les combinaisons...

Attention : On peut faire varier les 4 paramètres (dans l'exemple cible : 71, Catégorie 20, valeurs autorisées de 0 à 10) en changeant les valeurs de cCateg, cCible, ValAut(1) et (2). C'est peu testé sur d'autres réglages.

Cordialement

KD

Edit : voir post 7

 

[CBernardT]

Re : Combinaisons d'éléments avec maximum

Bonjour europeest, KenDev et le forum,

Pour ma part, le nombre de combinaisons possibles égal à : 3*3*3*4*3*3*2*4*4*4*11*11*11*6*6*6*6*6*6*6, soit 46 356 756 627 456. Nombre qui interdit l'affichage de toutes les combinaisons.

La somme des combinaisons évolue dans une fourchette de [0 à 88]. En effectuant une simple division, ce qui est faux et très approximatif, l'ordre du nombre de combinaisons dont la somme est 71 est de l'ordre de : X(Nbre de Combs / 88, soit 500 000 000 000 environ.

C'est la grandeur de ces nombres qui m'ont amené à réaliser un macro de recherche aléatoire de solution.

Peut-être qu'une explication de l'intérêt d'une somme égale à 71 apporterait un nouvel horizon à la discussion ?

 

[europeest]

Re : Combinaisons d'éléments avec maximum

Bonjour et merci a vos reponses KenDev et CBernardT

J'imaginais que l'eventail des combinaisons etait important, mais pas a ce point la....))

Ce travail porte sur une recherche theorique du choix optimal de nombres de magasins de 20 categories differentes dans une galerie commerciale qui doit comporter 71 magasins au total. C'est pourquoi nous avons etabli un seuil maximal de vraisemblance pour chaque categorie pour eviter de se retrouver avec 71 magasins de cosmetiques dans la galerie (par exemple pour la categorie A, pas plus de 2 magasins de ce type-ci).

Et dans cette recherche, une fois toutes les combinaisons calculees, et presentees dans le tableau (1 colonne pour chaque combinaison), il est possible de poursuivre les calculs pour etablir l'attractivite de chaque combinaison en fonction des attentes des habitants vivant autour de la galerie.

Voici pour la partie explicative. cela permet il de limiter le nombre de combinaisons et du temps de calcul?

Cordialement

 

[KenDev]

Re : Combinaisons d'éléments avec maximum

Bonjour à tous,

Mes excuses pour le précédent post, je n'y avais pas pris en compte les minimums et maximums individuels (les 20 catégories variaient de 0 à 10). D’où un nouveau fichier plus rapide. Renseigner la feuille Param et lancer la sub. Le masque par défaut est la traduction du classeur exemple. (On passe de 239457 schémas à 16696 et de 2346225261778251040 combinaisons à 2754315976 (uniquement les combinaisons valant 71). Toujours impensable à afficher mais on quitte l'astronomique.
Cordialement

KD

 

[europeest]

Re : Combinaisons d'éléments avec maximum

Rebonjour et merci pour la nouvelle macro KenDev

j'ai tente de la modifier (resultat en piece jointe) pour pouvoir y ajouter le nom des categories. Merci de m'indiquer si je n'ai pas detruit totalement la macro avec mes modifications...

Je l'ai fait tourner avec succes, jusqu'a 10 categories et un total de 20 boutiques. Pour le cas de figure de 20 categories, et un total de 71 boutiques, la macro est toujours en train de tourner, sans resultat jusqu'a present...

Trois questions
Pourquoi doit-on integrer les categories par ordre decroissant?
Que signifie dans la feuille de resultat le nombre indique dans la derniere colonne? Est-ce le parametre NbComb qui va écrire à droite de chacune des lignes précédentes le nombre de combinaisons correspondant à ce schéma? Donc si on fait la somme de la colomne NbComb, on a le nombre de combinaisons total, correct?
Avez-vous pu faire tourner la macro avec 20 categories, et un total de 71 boutiques? combien de temps cela prend il?

Cordialement

 

[KenDev]

Re : Combinaisons d'éléments avec maximum

Bonjour à tous,

Pourquoi doit-on integrer les categories par ordre decroissant?

A cause du paragraphe 'Tableau nbre d’occurrences max autorisées pour chaque valeur possible' et de ses conséquences je crois. Faire un essai avec des données qui, ordonnées, vous ont déjà donnée un résultat. J'ajouterai que j'ai de gros doutes sur le bon fonctionnement si plusieurs lignes dans Param avaient le même maximum.

Que signifie dans la feuille de resultat le nombre indique dans la derniere colonne? Est-ce le parametre NbComb qui va écrire à droite de chacune des lignes précédentes le nombre de combinaisons correspondant à ce schéma? Donc si on fait la somme de la colomne NbComb, on a le nombre de combinaisons total, correct?

Correct

Avez-vous pu faire tourner la macro avec 20 categories, et un total de 71 boutiques? combien de temps cela prend il?

Oui, une trentaine de secondes sur un vieux netbook. Dans le fichier que vous venez de transmettre les données sont incohérentes. Dans la cellule F4 (Catégories) il y avait une formule qui additionnait la colonne C (Occurrences). Elle a été remplacée par un 4 au lieu du 15 (7+3+2+3) attendu. Par catégorie j'entends donc la largeur d'un schéma (c.a.d le nombre de boutiques d'après vos explications).

j'ai tente de la modifier (resultat en piece jointe) pour pouvoir y ajouter le nom des catégories. Merci de m'indiquer si je n'ai pas detruit totalement la macro avec mes modifications...

Pas d'erreurs repérées, j'ai fait tourner avec les données originelles (et APRES retour de la formule en F4) et j'obtiens les mêmes résultats (16696 schémas, 2754315976 combinaisons).

Par ailleurs, j'ai ajouté un petit 'patch' (3 lignes de plus et une variable supplémentaire) pour le cas particulier ou nb de catégories = cible qui tournait à l'infini à cause du dernier schéma composé uniquement de 1. Le code modifié de la sub principale (version sans la colonne catégories ajoutée) :

Sub Schemas()

Dim w As Worksheet, p%(1 To 4), i%, c%, Tp%(), Ta%(), j%, Tb%(), r&, b As Boolean

    Application.Calculation = xlCalculationManual
    Application.ScreenUpdating = False
    
    Set w = Worksheets("Param")
    If ActiveSheet Is w Then Sheets.Add
    
    'Parametres individuels
    p(1) = w.Cells(2, 5) 'minmin
    p(2) = w.Cells(3, 5) 'maxmax
    p(3) = w.Cells(4, 5) 'nb de categories
    p(4) = w.Cells(1, 5) 'cible
    If Not (p(3) * p(1) <= p(4) And p(3) * p(2) >= p(4)) Then Exit Sub
    
    'Parametres tableau
    For i = 2 To w.Cells(Rows.Count, 1).End(xlUp).Row
        c = c + 1
        ReDim Preserve Tp(1 To 4, 1 To c)
        Tp(1, c) = w.Cells(i, 1) 'minimum
        Tp(2, c) = w.Cells(i, 2) 'maximum
        Tp(3, c) = w.Cells(i, 3) 'occurences
    Next i
    Tp(4, 1) = Tp(3, 1) 'cumul des occurences
    For i = 2 To c
        Tp(4, i) = Tp(4, i - 1) + Tp(3, i)
    Next i
    c = 0

    'Tableau nbre d'occurences max autorisées pour chaque valeur possible
    ReDim Ta(p(1) To p(2))
    For i = p(1) To p(2)
        For j = 1 To UBound(Tp, 2)
            If i >= Tp(1, j) And i <= Tp(2, j) Then
                Ta(i) = Ta(i) + Tp(3, j)
            End If
        Next j
    Next i
    
    'Schema de dépârt
    Tb = fCombinN1(p(2), p(3), p(4))
    
    Do
        If fFiltrage(Tp(), Tb(), Ta(), p(1), p(2)) Then
            r = r + 1: b = False
            For i = 1 To UBound(Tb)
                Cells(r, i) = Tb(i)
                If Tb(i) > 1 Then b = True
            Next i
            Cells(r, UBound(Tb) + 1) = NbComb(Tb, Tp())
            If Not b Then Exit Sub
        End If
        Tb = fNextSchema(Tb(), p(4))
        If Tb(1) = 0 Then Exit Do
    Loop
    
    Application.Calculation = xlCalculationAutomatic
    Application.ScreenUpdating = True
End Sub

Cordialement

KD

 

[europeest]

Re : Combinaisons d'éléments avec maximum

Bonjour et merci pour vos reponses.
J'ai integre la derniere modif VBA dans la macro, et tout fonctionne dans cette configuration (total 71, 20 categories, valeurs des categories entre 0 et 10), merci pour votre aide precieuse!

Questions subsidiaires...
1. Dans la feuille "Param", si l'on change les donnees de la colonne "Occurences" qu'est ce que cela entraine? Est ce que les valeurs dans la colonne occurence ont une influence sur le calcul final, ou sont elles juste editees a titre informatif?

2. Dans les calculs de combinaison, la macro propose pour chaque categorie des valeurs superieures a celles autorises. Peut on limiter les valeurs pour chaque categorie calculee en prenant en compte leur maximum (afin de minimiser le nombre de combinaisons a calculer)?
Par exemple dans la categorie C (maximum autorise 9), le calcul actuel prend en compte la valeur 10....

A vous lire
Cordialement

 

[KenDev]

Re : Combinaisons d'éléments avec maximum

Bonjour à tous,

Dans le fichier joint vous n'avez toujours pas rétabli la formule pour la case Categ.!
J'écrivais :

Dans le fichier que vous venez de transmettre les données sont incohérentes. Dans la cellule F4 (Catégories) il y avait une formule qui additionnait la colonne C (Occurrences). Elle a été remplacée par un 4 au lieu du 15 (7+3+2+3) attendu. Par catégorie j'entends donc la largeur d'un schéma (c.a.d le nombre de boutiques d'après vos explications).

La case Categ devrait contenir 95 et non 20 (Categ.=SOMME DES OCCURENCES).

J'écrivais aussi :

J'ajouterai que j'ai de gros doutes sur le bon fonctionnement si plusieurs lignes dans Param avaient le même maximum.

Dans le fichier transmis je vois (un exemple parmi beaucoup) un 0-7-7 précédent un 0-7-5. -> Il fallait écrire une seule ligne 0-7-12!

Dans la feuille "Param", si l'on change les donnees de la colonne "Occurences" qu'est ce que cela entraine? Est ce que les valeurs dans la colonne occurence ont une influence sur le calcul final, ou sont elles juste editees a titre informatif?

Je ne sais quoi répondre.

Dans les calculs de combinaison, la macro propose pour chaque categorie des valeurs superieures a celles autorises. Peut on limiter les valeurs pour chaque categorie calculee en prenant en compte leur maximum (afin de minimiser le nombre de combinaisons a calculer)?
Par exemple dans la categorie C (maximum autorise 9), le calcul actuel prend en compte la valeur 10....

Curieusement je n'ai pas ce souci. Voir premier paragraphe.

J'arrête là avec les tentatives d'explications. Je transmet quand même un nouveau fichier avec des contrôles (la sub vous avertira en cas d'entrées fantaisistes) et j'y ajoute la possibilité de maximums identiques (0-7-7 précédent un 0-7-5 sera dorénavant possible). Disparition des cases MinMin, MaxMax et Categ qui semblent vous contrarier.

D(un point de vue plus général ce fichier (et les précédents) peuvent lister les partitions d'un entier. Par exemple pour avoir la liste des partitions de 7, écrire une seule ligne dans la feuille param. Minimum = 0, Maximum=Occurrences=Cible=7. La colonne catégorie ne sert à rien.

Cordialement

KD

 

[europeest]

Re : Combinaisons d'éléments avec maximum

Bonjour et merci pour votre reponse.
Tout fonctionne bien, et reussi a tester pour differentes hypotheses.

Encore merci pour votre aide, et votre patience.
Cordialement

 

[europeest]

Re : Combinaisons d'éléments avec maximum - RunTime Error 6 - Overflow

Bonjour a tous.

J'ai essaye de modifier l'exercice en augmentant la quantite maximale de boutiques par categories - toujours 20 categories (desormais le maximum de boutiques par categorie est de 20 au lieu de 10).
Lorsque je lance la macro, il s'affiche une erreur Runtime 6 - Overflow des que le nombre de resultats (lignes) dans la feuille de resultats depasse 32 767.

En regardant sur le forum, il semble que ce soit lie a une question de denomination de champ (Long au lieu d'Integer), mais je n'ai pas reussi a modifier la VBA pour corriger ce point. Des idees pour corriger ce point et permettre d'afficher jusqu'a un million de lignes (maximum de Excel 2010)?

Cordialement

 

[moles]

Re : Combinaisons d'éléments avec maximum - RunTime Error 6 - Overflow

Bonjour
Je cherche en vain depuis un moment à connaitre l’ensemble des combinaisons possible de 7 chiffres qui peuvent être composé de 2,3,4,5,6 ou 7 éléments.
De plus leur combinaisons doit se faire par ordre croissant.

Par exemple une classe de 7 élèves.
Je souhaite les classer du plus petit au plus grand par groupe de 2 à 7 éléves

Par exemple 1-2-3-4-5-6-7
Je peux former :
1-2
1-2-3
1-2-3-4
…
1-2-3-4-5-6-7
1-3
1-3-4
...

Toute aide est la bienvenue !

Merci !!!

 

[moles]

Re : Combinaisons d'éléments avec maximum - RunTime Error 6 - Overflow

Bonjour
Je cherche en vain depuis un moment à connaitre l’ensemble des combinaisons possible de 7 chiffres qui peuvent être composé de 2,3,4,5,6 ou 7 éléments.
De plus leur combinaisons doit se faire par ordre croissant.

Par exemple une classe de 7 élèves.
Je souhaite les classer du plus petit au plus grand par groupe de 2 à 7 éléves

Par exemple 1-2-3-4-5-6-7
Je peux former :
1-2
1-2-3
1-2-3-4
…
1-2-3-4-5-6-7
1-3
1-3-4
...

Toute aide est la bienvenue !

Merci !!!

une réponse ???