Aucune combinaison possible ? Ça paraît dingue

**Mike888** · 11/11/2017, 11h58

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** · 11/11/2017, 12h26

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** · 11/11/2017, 12h28

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** · 11/11/2017, 12h29

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

**Mike888** · 11/11/2017, 12h32

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** · 11/11/2017, 12h33

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** · 11/11/2017, 12h43

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** · 11/11/2017, 15h11

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

**wiwaxia** · 11/11/2017, 16h31

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** · 11/11/2017, 16h55

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** · 11/11/2017, 17h07

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à !