Discussion :

[Mike888]

Salut !

Contexte du problème :

Dans ma famille, à Noël, nous (13 personnes) faisons chacun des listes de cadeaux qui nous feraient plaisir, puis nous échangeons nos listes au hasard. Chacun a donc la liste de quelqu'un d'autre (hormis son conjoint).
Pour cette année, j'ai décidé que l'on changerait un peu le système. En effet, plutôt que de tirer la liste complète de quelqu'un, chacun obtiendrait une liste avec des cadeaux venant de listes différentes. Jusque là, tout va bien.

J'ai donc conçu un programme qui se charge de cela. Mais voilà, mon programme ne trouve aucune combinaison possible... Je l'ai laissé tourner pendant des heures, il a effectué plus de 116 millions de tirages sans en trouver un seul qui satisfasse aux conditions requises. Ca paraît incroyable...

Donc, entre autres conditions, il faut que les listes que l'on tire fassent entre 22 et 28€. Et de même, le montant des cadeaux que l'on reçoit doit également faire entre 22 et 28€. Et c'est avec cette dernière condition que ça coince ! Comment est-ce possible qu'il n'y parvienne pas ? J'ai vérifié l'algorithme je ne sais pas combien de fois et tout semble correct...

Ce que je voudrais savoir, c'est si, mathématiquement parlant, c'est un problème impossible à résoudre ?

Merci pour vos lumières !

[valentin03]

Le problème c'est les conditions (s'il n'y a pas de bug dans "<"; ">")
Elargis les fourchettes jusqu'à ce que ça passe; ou fais à l'envers en partant de fourchettes larges et en réduisant.
Tu peux vérifier en by-passant les conditions.

[Mike888]

J'ai oublié de mentionner qu'il y avait 70 articles (cadeaux) au total.
D'autre part, au plus j'augmente la fourchette correspondant au montant des cadeaux reçus, au plus vite le programme trouve une combinaison (ce qui est normal). Mais quand je spécifie 22 et 28 comme limites, là, il ne semble rien trouver... Est-ce normal ?

[Mike888]

Valentin, tu as répondu pendant que je postais moi-même

[Mike888]

J'ai testé entre temps, avec 15 (au lieu de 22) et 35 (au lieu de 28) et le prog a trouvé un bon tirage au bout de 280000 essais ! Y'a de l'espoir !

[wiwaxia]

Bonjour

Il manque des données dans ton énoncé:

Dans ma famille, à Noël, nous (13 personnes) ... Chacun a donc la liste de quelqu'un d'autre (hormis son conjoint).

Combien y a-t-il de couples ? Et de personnes seules ?

... chacun obtiendrait une liste avec des cadeaux venant de listes différentes ...

Combien de cadeaux
a) figurent-ils sur une liste ?
b) chaque personne offre-t-elle en tout, aux autres membres du groupe ?

[Mike888]

Il y a 5 couples et 3 célibataires.
Il y a 70 cadeaux encodés au total.
Une personne offre au maximum 5 articles.

Merci pour ton intérêt !

[valentin03]

Comme ton algo a l'air de fonctionner, tu pourrais le poster, ça pourrait servir à d'autres.

[wiwaxia]

Je comprends vite, mais il faut bien m'expliquer .

Donc ... il faut que les listes que l'on tire fassent entre 22 et 28€. Et de même, le montant des cadeaux que l'on reçoit doit également faire entre 22 et 28€

Donc:
a) le prix total des listes, comme celui des cadeaux, est compris entre 22 et 28 €;
b) le prix de chaque cadeau est obligatoirement compris entre 22/5 = 4.4 = 5 € (en arrondissant à l'entier supérieur) et 28 €;
c) un cadeau donné ne peut être offert plusieurs fois.

L'ensemble des cadeaux, comme celui des donneurs, peut être représenté par une matrice d'entiers au format byte:

Code :

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

1
2
3
4
5
6
7
CONST NtotC = 70; NtotP = 13;
 
TYPE Tab_70 = ARRAY[1..NtotC, 0..2] OF Byte;
TYPE Tab_13 = ARRAY[1..NtotP, 0..1] OF Byte;
 
VAR ListeC: Tab_70;
    ListeP: Tab_13;

étant admises les conventions suivantes:

Code :

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

1
2
ListeC[i, 0]: Prix du cadeau ;  ListeC[i, 1]: Donateur ; ListeC[i, 2]: Bénéficiaire ;
ListeP[i, 0]: Prix total payé ; ListeC[i, 1]: Nombre de cadeaux offerts ;

1°) Un premier tirage aléatoire (ou l'introduction d'une liste constante), accompagné de la mise à zéro des autres termes, permet l'initialisation de la première matrice:

Code :

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

1
2
3
4
5
6
7
8
9
10
PROCEDURE Init_LC(VAR L_: Tab_70);
  VAR i, m: Byte; Lc: Tab_70;
  BEGIN
    Randomize;
    FOR i:= 1 TO NtotC DO BEGIN
                            m:= Random(24); Lc[i, 0]:= m + 5;          // 5 <= Prix <= 5 +23 = 28
                            Lc[i, 1]:= 0; Lc[i, 2]:= 0;                   
                          END;
    L_:= Lc
  END;

2°) Un second tirage simule les choix de toutes les personnes, qui sélectionnent un nouveau cadeau jusqu'à la vérifcation des conditions: ((22 <= Prix total <= 28) et (Ncad <= 5)), et en évitant de prendre un objet déjà réservé.

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
16
17
18
19
 
PROCEDURE ChoixC(VAR L_p: Tab_13; VAR L_c: Tab_70);
  VAR i, j, k, Ncad, PrixT: Byte;
  BEGIN
    FOR i:= 1 TO NtotP DO
      FOR j:= 0 TO 1 DO L_p[i, j]:= 0;           // Mise à zéro de tous les termes
    FOR i:= 1 TO NtotP DO
      BEGIN
        Ncad:= 0; PrixT:= 0;
        REPEAT
          REPEAT
            k:= Random[NtotC); Inc(k);
          UNTIL (L_c[k, 2]=0);                   // Tirage d'un objet non réservé
          Inc(Ncad); Inc(PrixT, L_c[k]
        UNTIL ((22<=PrixT) AND (PrixT<=28)) OR (Ncad=5);
        L_c[k, 2]:= i;                           // Réservation du cadeau par le bénéficiaire potentiel (i)  
        L_P[i, 1]:= PrixT; L_P[i, 2]:= Ncad      // Mémorisation du prix payé et du nombre de cadeaux
      END;
  END;

L'appel des deux procédures sera fait par les instructions:

Code :

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

1
2
Init_LC(ListeC);
ChoixC(ListeP, ListeC);

Il vaut mieux que je m'arrête à ce stade, des bourdes ayant pu s'accumuler en l'absence de compilation.

Reste à coder la répartition aléatoire des donneurs sur les cadeaux sélectionnés, en attribuant une valeur positive aux éléments ListeC[i, 1] de la première matrice, sous réserve des restrictions:
a) ListeC[k, 1] <> ListeC[p, 2] : pas de cadeau à soi-même, cela nuit à l'amblaince;
b) ListeC[p, 1]² + ListeC[p, 1]² <> 5, 25, 61, 113 et 181 : pas de cadeaux entre conjoints ((1, 2) ; (3, 4) ; (5, 6) ; (7, 8) ; (9, 10)); vérifier l'exclusivité de cette condition écrite à l'improviste.

Vous n'allez pas vous ennuyer, à Noël

[Mike888]

Oulalalah...
Je ne saisis pas trop bien tout ce que tu as écrit ci-dessus...

En fait, je voulais juste savoir si c'était possible qu'aucun tirage validant les conditions ne sorte... même après un nombre incroyable d'essais !

Ah oui, le montant d'un article va de 1€ à 28€.
Et pour rappel, le montant d'une liste tirée par le programme et attribuée à une personne va de 22€ à 28€.
Le montant total des cadeaux qu'on reçoit va de 22€ à 28€.
Le nombre maximum de cadeaux qu'on a sur la liste que l'on reçoit par le programme est de 5 (au minimum, il y a en 1).
Une personne ne peut avoir de cadeaux de son conjoint ou de soi-même sur la liste qu'elle reçoit.
Un cadeau ne peut être tiré plus d'une fois.
Tous les cadeaux ne sont pas nécessairement tirés.

Dans mon cas, il y a 70 articles encodés par les personnes. Il y a 13 personnes, dont 5 couples.

Voici mon code (écrit en C#) :

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
            int cptgeneral = 0;
            label1.Visible = true;
            checkBox1.Enabled = false;
            Random rand = new Random();
            Double montantliste = 0;
            Double checkmontantliste = 0;
            int cstmontantinfliste = 22;
            int cstmontantsupliste = 28;
            int cstmontantrecuinf = 22;
            int cstmontantrecusup = 28;
            int nbmaxarticlesparlistetiree = 5;
            Boolean test = false;
            Boolean resetboucle = false;
            int j = 0;
            int k = 0;
            int cptnbarticles = 0;
            int cptnbarticlesparliste = 0;
            int cptpersonnes = 0;
            int nbarticletotal = 0;
            int checkcptnbarticlesparliste = 0;
            int nbtotalpersonnes = BL.PersonneBL.CombienPersonnes();
            List<BO.PersonneBO> Lalistepersonnes;
            PersonneBO objpersonne;
            Lalistepersonnes = BL.PersonneBL.SelectAllListPersonne();
            Lalistepersonnes.Sort();
            List<ArticleBO> Lalistearticles;
            Lalistearticles = BL.ArticleBL.SelectAllListArticle();
            List<ArticleBO>[] Tablist = new List<ArticleBO>[nbtotalpersonnes];
            for (int i = 0; i < Tablist.Length; i++) Tablist[i] = new List<ArticleBO>();
            nbarticletotal = Lalistearticles.Count();
            int[] Tabdejapris = new int[nbarticletotal];
            do
            {
                for (int i = 0; i < nbarticletotal; i++) Tabdejapris[i] = 0;
                resetboucle = false;
                cptnbarticles = 0;
                cptpersonnes = 0;
                do
                {
                    cptnbarticlesparliste = 0;
                    montantliste = 0;
                    do
                    {
                        k = 0;
                        test = false;
                        do
                        {
                            if (Lalistearticles[k].Prix <= (cstmontantsupliste - montantliste) && Tabdejapris[k] == 0) test = true;
                            k++;
                        }
                        while (k < nbarticletotal && test == false);
                        if (test == true)
                        {
                            j = rand.Next(nbarticletotal);
                            if (Tabdejapris[j] == 0)
                            {
                                if (montantliste + Lalistearticles[j].Prix <= cstmontantsupliste)
                                {
                                    objpersonne = BL.PersonneBL.QuellePersonne(Lalistearticles[j].IdArticle);
                                    if (objpersonne.IdPersonne != Lalistepersonnes[cptpersonnes].IdPersonne)
                                    {
                                        if (checkBox1.Checked == true)
                                        {
                                            if (objpersonne.IdConjoint != Lalistepersonnes[cptpersonnes].IdPersonne)
                                            {
                                                Tabdejapris[j] = 1;
                                                montantliste += Lalistearticles[j].Prix;
                                                Tablist[cptpersonnes].Insert(cptnbarticlesparliste, Lalistearticles[j]);
                                                cptnbarticlesparliste++;
                                                cptnbarticles++;
                                            }
                                            else test = false;
                                        }
                                        else
                                        {
                                            Tabdejapris[j] = 1;
                                            montantliste += Lalistearticles[j].Prix;
                                            Tablist[cptpersonnes].Insert(cptnbarticlesparliste, Lalistearticles[j]);
                                            cptnbarticlesparliste++;
                                            cptnbarticles++;
                                        }
                                    }
                                    else test = false;
                                }
                            }
                        }
                    }
                    while (montantliste <= cstmontantinfliste && cptnbarticles < nbarticletotal && test == true);
                    cptpersonnes++;
                    if (test == false || cptnbarticles >= nbarticletotal) resetboucle = true;
                }
                while (cptpersonnes < nbtotalpersonnes && resetboucle == false);
                if (resetboucle == false)
                {
                    for (int i = 0; i < nbtotalpersonnes; i++)
                    {
                        checkcptnbarticlesparliste = 0;
                        checkmontantliste = 0;
                        foreach (ArticleBO obja in Tablist[i])
                        {
                            checkcptnbarticlesparliste++;
                            checkmontantliste += obja.Prix;
                        }
                        if (checkcptnbarticlesparliste > nbmaxarticlesparlistetiree || checkmontantliste <= cstmontantinfliste)
                        {
                            resetboucle = true;                            
                        }
                    }
                }
                if (resetboucle == false)
                {
                    for (int i = 0; i < nbtotalpersonnes; i++)
                    {
                        foreach (ArticleBO objar in Tablist[i])
                        {
                            PersonneBO objpe = BL.PersonneBL.QuellePersonne(objar.IdArticle);                                                                                                               
                            for (int l = 0; l < nbtotalpersonnes; l++)
                            {
                                if (objpe.IdPersonne == Lalistepersonnes[l].IdPersonne)
                                {
                                    Lalistepersonnes[l].Montant_recu += objar.Prix;                                    
                                }
                            }                            
                        }
                    }
                    for (int i = 0; i < nbtotalpersonnes; i++)
                    {
                        if (Lalistepersonnes[i].Montant_recu < cstmontantrecuinf || Lalistepersonnes[i].Montant_recu > cstmontantrecusup)
                        {
                            resetboucle = true;                            
                        }                        
                    }
                }
                if (resetboucle == true)
                {
                    for (int i = 0; i < nbtotalpersonnes; i++)
                    {
                        Tablist[i].Clear();
                        Lalistepersonnes[i].Montant_recu = 0;
                    }
                    cptgeneral++;                    
                }
            }
            while (resetboucle == true);

Voilà, ce sera certainement très obscur et compliqué à décortiquer pour celui qui veut lire; d'autre part, il y a surement de gros défauts dans l'écriture, je le conçois sans problèmes !

[Mike888]

Donc, en gros, ce que fait ce morceau de code, c'est de créer 13 listes de cadeaux parallèlement à une liste de 13 personnes; un peu plus loin dans le code (non publié ci-dessus), on attribue une liste de cadeaux à chaque personne !

La 1ère partie du code (jusqu'à la ligne 92) crée 13 listes de cadeaux; les deux blocs de code suivants vérifient qu'une liste contient 5 cadeaux max, que le montant de chaque liste générée ne dépasse pas 28€ et que le montant de cadeaux reçus soit entre 22 et 28€.

Si la variable "test" vaut à un moment donné "false" et/ou "resetboucle" vaut "true", le tirage est considéré comme mauvais et on recommence !

Voilà !

[wiwaxia]

J'ai codé l'étalement des prix de 5 à 28 € pour éviter un coût total sur 5 tirages inférieur à 22 € (5 * 4 = 20 €).

Ah oui, le montant d'un article va de 1€ à 28€.

Le programme doit normalement conduire à une solution conforme. Il se lit pratiquement comme du pseudo-code.

Pour n'avoir quasiment rien obtenu,

... il a effectué plus de 116 millions de tirages sans en trouver un seul ...

tu as sûrement mis quelque part des conditions incompatibles.
Regarde celles qui concernent les prix.

[Mike888]

J'ai codé l'étalement des prix de 5 à 28 € pour éviter un coût total sur 5 tirages inférieur à 22 € (5 * 4 = 20 €).


Le programme doit normalement conduire à une solution conforme. Il se lit pratiquement comme du pseudo-code.

Pour n'avoir quasiment rien obtenu,

tu as sûrement mis quelque part des conditions incompatibles.
Regarde celles qui concernent les prix.

Mais comment comprendre qu'avec par exemple une fourchette de 16/34 (au lieu de 22/28), ça fonctionne alors ?

[wiwaxia]

... ce que fait ce morceau de code, c'est de créer 13 listes de cadeaux parallèlement à une liste de 13 personnes ...

Pourquoi 13 listes ? Elles n'ont aucun élément commun, du fait de l'attribution des cadeaux à un destinataire unique; il est beaucoup plus simple de consigner ce dernier dans la "liste" des cadeaux (qui sera une matrice - solution adoptée - ou une liste d'enregistrements).
Ton code doit être épouvantablement compliqué.

# PS:

J'ai testé entre temps, avec 15 (au lieu de 22) et 35 (au lieu de 28) et le prog a trouvé un bon tirage au bout de 280000 essais

Avec un semblable rendement (1 / 280000) les conditions de sélection sont vraiment trop sévères !

[wiwaxia]

Si tu procèdes en gros à 5*13 = 65 tirages indépendants sur les 70 cadeaux disponibles, tu as toutes chances de tirer au moins 2 fois le même, sans même parler des conditions sur les coûts ... Il n'est pas étonnant, dans ces conditions, que cela ne donne rien.
La probabilité de tirer 65 cadeaux différents est
p = (70/70)*(69/70)*(68/70)*(67/70)* ... *(6/70) = (70!)/(5!*70⁶⁵) = 1.197857E¹⁰⁰/(1.2E²*1.435036E¹²⁹) = 0.695602E^-31 (d'après ma calculette).
Autant dire que c'est perdu d'avance ... même si ton code est par ailleurs correct.

Mon programme, qui n'a rien d'extraordinaire, fonctionne (enfin, j'espère ...) parce que les conditions de sélection interviennent à chaque tirage.

#

Mais comment comprendre qu'avec par exemple une fourchette de 16/34 (au lieu de 22/28), ça fonctionne alors ?

Parce que le prix total pouvant descendre à 5*1 = 5 € , la probabilité d'un tirage acceptable est fortement augmentée si tu abaisses le seuil inférieur de 22 à 16 €.

[Mike888]

D'accord, mais il y a des tests que je ne peux faire qu'en fin de tirage et pas à chaque sélection de cadeaux...

[valentin03]

Tel quel l'algo tourne tant qu'il n'y a pas de solution.
Pour être sûr qu'il n'y en a pas il faut lui faire explorer toutes les combinaisons, mettre un renvoi d'info en fin d'exploration et attendre la fin.
Mais il faudrait calculer le nombre de combinaisons pour savoir à quoi s'attendre en temps de calcul.

[wiwaxia]

Il y a pour l'essentiel deux sortes de tirages sous condition:
a) le choix des cadeaux par les bénéficiaires, qui doit s'accompagner d'une marque de réservation afin que les objets ne soient pas demandés plusieurs fois - j'ai tenté de montrer à quelle impasse pouvait conduire une série de tirages indépendants; d'où la nécessité d'attribuer à chaque cadeau au moins deux paramètres: le prix, plus une autre grandeur permettant de savoir s'il a déjà été choisi.
b) la répartition aléatoire des cadeaux sélectionnés sur les donneurs, que je n'ai pas codée, mais dont les contraintes sont beaucoup moins sélectives (il s'agit des incompatibilités de personnes, qui ont été sommairement évoquées).

La procédure ChoixC(ListeP, ListeC) a été écrite et sommairement commentée; si la personne de rang (11) porte son choix sur le 51^ème objet valant 25 €, la ligne correspondante passe de
< ListeC[51, 0] = 25 , ListeC[51, 1] = 0 , ListeC[51, 2] = 0 > à
< ListeC[51, 0] = 25 , ListeC[51, 1] = 0 , ListeC[51, 2] = 11 > ;
le 3^me élément devient positif, marquant ainsi la réservation du cadeau.
Cette condition d'attribution unique se retrouve dans la même procédure:

Code :

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

1
2
3
          REPEAT
            k:= Random[NtotC); Inc(k);
          UNTIL (L_c[k, 2]=0);

Il y a un ordre de priorité implicite que j'ai allègrement négligé: les cadeaux sont successivement réservés par les personnes de rang ( 1 > 2 > 3 > ... > 13 ) ; rien n'interdit d'employer une liste constante I1[i], pour insérer une permutation appropriée des 13 premiers entiers et définir un nouvel ordre de priorité décroissante:

Code :

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

CONST I1: Tab_13 = (5, 8, 11, 12, 1, 3, 4, 9, 13, 2, 6, 7, 10);

La procédure décrite deviendrait:

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
16
17
18
19
20
PROCEDURE ChoixC(VAR L_p: Tab_13; VAR L_c: Tab_70);
  CONST I1: Tab_13 = (5, 8, 11, 12, 1, 3, 4, 9, 13, 2, 6, 7, 10);
  VAR i, j, k, Ncad, PrixT: Byte;
  BEGIN
    FOR i:= 1 TO NtotP DO
      FOR j:= 0 TO 1 DO L_p[i, j]:= 0;           // Mise à zéro de tous les termes
    FOR i:= 1 TO NtotP DO
      BEGIN
        Ncad:= 0; PrixT:= 0;
        REPEAT
          REPEAT
            k:= Random[NtotC); Inc(k);
          UNTIL (L_c[k, 2]=0);                   // Tirage d'un objet non réservé
          Inc(Ncad); Inc(PrixT, L_c[k]
        UNTIL ((22<=PrixT) AND (PrixT<=28)) OR (Ncad=5);
        L_c[k, 2]:= I1[i];                               // Réservation du cadeau par le bénéficiaire potentiel (i)  
        L_P[I1[i], 1]:= PrixT; L_P[I1[i], 2]:= Ncad      // Mémorisation du prix payé et du nombre de cadeaux
      END;
  END;

[Mike888]

Wiwaxia, tu as une capacité d'abstraction très étonnante !...
Je vais être sincère et d'ailleurs, ça me peine franchement, mais je ne comprends pas la moitié de ce que tu racontes !

[wiwaxia]

J'en suis sincèrement désolé, moi aussi ... Faute de temps, la rédaction du dernier message (que je viens de compléter) était en effet menée au pas de charge.

Je me doute que le déchiffrement d'un programme peut se révéler éreintant. Peux-tu au moins saisir le plan de ce qui est proposé ? Je pourrais toujours rajouter des précisions, là où cela pourrait être nécessaire.

D'autant que le programme que tu as toi-même mis au point semble fonctionner; la faiblesse rédhibitoire de son rendement vient sans doute de l'ordre défectueux dans lequel interviennent les restrictions.
Mais cela te demandera un sacré travail, parce qu'il te faudra reprendre toute la structure de l'ensemble.