Partage

[Probabilités] exo euler 151

mon approche est elle correcte ?

Sujet résolu

2 août 2011 à 9:16:29

Bonjour,

Je suis en train de plancher sur le problème 151 du project Euler. J'ai mis l'énoncé original (en) en secret :

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .

Mon approche est la suivante : le nombre de fois par semaine où l'on va ouvrir une enveloppe contenant une unique feuille équivaut la somme des probabilités d'ouvrir une telle enveloppe à chaque étape (étape 1 et 16 exclues).

Algorithme :

énumérer récursivement toutes les possibilités.
au cours de l'énumération, compter dans un tableau <math>\(tab\)</math>, avec <math>\(n\)</math> correspondant au numéro de job (1er, 2e, etc.) :
- <math>\(tab_n_t\)</math> le nombre total d'enveloppes possibles à l'étape <math>\(n\)</math>;
- <math>\(tab_n_s\)</math> le nombre d'enveloppes ne contenant qu'une feuille à l'étape <math>\(n\)</math>.
ensuite, pour chaque élément du tableau, je pose : <math>\(P_n = \frac{tab_n_s}{tab_n_t}\)</math>
(<math>\(P_n\)</math> -> probabilité d'avoir une enveloppe contenant une seule feuille à l'étape <math>\(n\)</math>)
et enfin, je calcule <math>\(\sum_{k = 2}^{n-1} P_k\)</math> , censé me donner la (bonne) réponse.

Concrètement, pour donner un exemple, ça donne quelque chose comme ça, pour une enveloppe originale contenant une feuille A2 :

tab = [[1, 1], [1, 0], [3, 0], [9, 0], [27, 3], [75, 0], [180, 45], [315, 315]]
P =   [1.0, 0.0, 0.0, 0.0, 0.11, 0.0, 0.25, 1.0]
0.361111

Comme vous devez vous douter, mon résultat est faux.

Après moult tests, je crois que c'est l'approche qui est incorrecte, je fais donc appel à vos lumières : pourquoi mon approche est fausse pour le problème posé ? quelle(s) approche(s) adopter ? (prière de me pas me donner de réponse mâchée, simplement des éclaircissements).

Merci !

EDIT : reformulation, en utilisant les balises math.

Anonyme

3 août 2011 à 10:43:56

Bonjour,

Citation

Comme vous devez vous douter, mon résultat est faux.

Si c'est toi qui le dis, je te contredirai pas

En fait tu décris un principe de décompte qui parait logique mais j'ai un peu de mal à suivre ton exemple pour juger de la fausseté.
(Quand tu dis c'est faux, c'est parce que tu connais le résultat à trouver ou c'est purement "intuitif" ?)

Si j'ai correctement compris le processus décrit..., je propose une piste possible, pour voir si ça correspond à ce que tu fais ou pour t'aider à trouver une erreur éventuelle.

C'est lourd mais a priori systématique et exhaustif...

Je considère la matrice suivante:
<math>\(\[M_{4 = } \begin{pmatrix} -1&1&1&1 \\ 0&-1&1&1 \\ 0&0&-1&1 \\ 0&0&0&-1 \\ \end{pmatrix} \]\)</math>
Elle représente les conséquences du retrait d'un format A5 en fonction du format tiré. 1ére ligne retrait de A2 qui rajoute dans l'enveloppe 1 A3,1 A4, 1 A5, deuxième ligne retrait d'un A3 qui rajoute 1 A2 et 1 A5 etc...
La situation de départ aprés retrait du premier A5 est caractérisée par <math>\(\[E_{[15,1] = } \begin{pmatrix} 1&1&1&1 \\ \end{pmatrix} \]\)</math> chaque colonne des matrices E y représente le nombre de feuilles par format décroissant.
Les possibilités de l'étape suivantes sont alors:
<math>\(\[E_{[14,4] = } \begin{pmatrix} 0&2&2&2 \\ 1&0&2&2 \\ 1&1&0&2 \\ 1&1&1&0 \\ \end{pmatrix} \]\)</math> obtenues en ajoutant la ligne E à chaque ligne de la matrice de transformation M, on obtient ainsi les situations possibles de l'étape suivante.
Chaque ligne de la nouvelle matrice E va se voir appliquer la transformation par M. Le nombre de situation croit donc en principe selon une progression géométrique de raison 4, mais en fait sensiblement moins, car chaque fois que apparait -1, c'est une situation impossible non retenue.
Je donne juste l'étape suivante qui comprend 12 cas et non 16.
<math>\(\[E_{[13,12] = } \begin{pmatrix} 0&1&3&3 \\ 0&2&1&3 \\ 0&2&2&1 \\ 1&0&1&3 \\ 1&0&2&1 \\ 0&2&1&3 \\ 1&0&1&3 \\ 1&1&0&1 \\ 0&2&2&1 \\ 1&0&2&1 \\ 1&1&0&1 \\ \end{pmatrix} \]\)</math>.
Si on stocke l'addition des lignes de ces matrices, on obtient la distribution exhaustive du nombre de feuilles présentes pour chaque situation possible à chaque étape, dont celle où elle vaut 1 évidemment.
L'algorithme associé ne me semble pas compliqué à programmer, mais brut de forge tel que décrit lourd en stochage mémoire.

yoch

3 août 2011 à 11:24:46

Merci pour ta réponse, je commençais à me sentir seul...

Citation : nabucos

Citation

Comme vous devez vous douter, mon résultat est faux.

Si c'est toi qui le dis, je te contredirai pas

En fait tu décris un principe de décompte qui parait logique mais j'ai un peu de mal à suivre ton exemple pour juger de la fausseté.
(Quand tu dis c'est faux, c'est parce que tu connais le résultat à trouver ou c'est purement "intuitif" ?)

1. mon résultat ne passe pas.
2. sur un certain site, ils donnent la solution, qui est loin de la mienne.

En fait, j'ai écrit un code naïf et un code optimisé. Le code naïf m'a servi à faire des tests unitaires sur un volume de données plus petit, et ainsi tester la fiabilité de mon 2e code. Il semble totalement fiable, pourtant la réponse est fausse, je ne comprends pas où ça coince...

Pour mon exemple, je prends une enveloppe initiale contenant une feuille A2 (donc 8 étapes), et je donne la table des probabilités pour chaque étape (2e ligne), et le résultat (0.361 fois en moyenne).

Citation : nabucos

Si j'ai correctement compris le processus décrit..., je propose une piste possible, pour voir si ça correspond à ce que tu fais ou pour t'aider à trouver une erreur éventuelle.

C'est lourd mais a priori systématique et exhaustif...
[...]

J'aime beaucoup ton idée. Mais il me semble qu'il y a un problème avec les "doublons". Je veux dire que ta technique permets de connaitre le nombre de configurations à une étape donnée, pas leur fréquence (une même configuration pouvant être obtenue de diverses manières, je prends un exemple, pour la première ligne de <math>\(\[E_{[14,4]\)</math> tu auras au maximum 4 possibilités, alors que l'enveloppe contient 6 feuilles).

Chez moi, je trouve 18 possibilités à l’étape 13 (contre 12 possibilités chez toi), ce qui correspond bien à la somme de <math>\(\[E_{[14,4]\)</math> :

('a1',)
.. ('a2', 'a3', 'a4', 'a5')
.... ('a3', 'a3', 'a4', 'a4', 'a5', 'a5')
...... ('a3', 'a4', 'a4', 'a4', 'a5', 'a5', 'a5')
...... ('a3', 'a4', 'a4', 'a4', 'a5', 'a5', 'a5')
...... ('a3', 'a3', 'a4', 'a5', 'a5', 'a5')
...... ('a3', 'a3', 'a4', 'a5', 'a5', 'a5')
...... ('a3', 'a3', 'a4', 'a4', 'a5')
...... ('a3', 'a3', 'a4', 'a4', 'a5')
.... ('a2', 'a4', 'a4', 'a5', 'a5')
...... ('a3', 'a4', 'a4', 'a4', 'a5', 'a5', 'a5')
...... ('a2', 'a4', 'a5', 'a5', 'a5')
...... ('a2', 'a4', 'a5', 'a5', 'a5')
...... ('a2', 'a4', 'a4', 'a5')
...... ('a2', 'a4', 'a4', 'a5')
.... ('a2', 'a3', 'a5', 'a5')
...... ('a3', 'a3', 'a4', 'a5', 'a5', 'a5')
...... ('a2', 'a4', 'a5', 'a5', 'a5')
...... ('a2', 'a3', 'a5')
...... ('a2', 'a3', 'a5')
.... ('a2', 'a3', 'a4')
...... ('a3', 'a3', 'a4', 'a4', 'a5')
...... ('a2', 'a4', 'a4', 'a5')
...... ('a2', 'a3', 'a5')

Encore merci !

PS : dernier point (à toutes fins utiles) : mon niveau en math n'est vraiment pas élevé, il se peut que je dise n'importe quoi ou que j'emploie des termes incorrects, dans ce cas pas taper trop fort svp. :-°

bluestorm

3 août 2011 à 14:02:46

Il me semble que la façon de faire est correcte, et que le bug doit se situer plutôt dans tes algorithmes de calcul du nombre d'enveloppe possible et cie.

Ce n'est pas complètement évident que l'espérance du nombre de tirages vérifiant un critère est égale à la somme des probabilités, pour chaque tirage, qu'il vérifie ce critère. Mais c'est vrai.

On peut modéliser chaque tirage par une variable aléatoire <math>\(X_i\)</math>: <math>\(X_1, X_2... X_16\)</math>. Quand on dit "variable aléatoire" il s'agit en fait de fonctions qui dépendent de situation <math>\(\omega\)</math> appartenant à l'ensemble des situations possibles <math>\(\Omega\)</math> : <math>\(X_3(\omega)\)</math> est le nombre de feuilles présentes dans l'enveloppe au troisième tirage, dans la situation <math>\(\omega\)</math> (une "situation" représente ici un des univers possible, si tu veux, où tous les tirages ont été fait à l'avance et sont déterminés).

On cherche à calculer <math>\(E(\#\{i | X_i = 1\})\)</math>, l'espérance du nombre de tirages <math>\(X_i\)</math> où il n'y avait qu'une seule feuille dans l'enveloppe (<math>\(\#E\)</math> est le cardinal, le nombre d'éléments de l'ensemble E). Par définition de l'espérance, c'est égal à

<math>\(\sum_{\omega \in \Omega} \#\{i | X_i(\omega) = 1\} * P(\omega)\)</math>

C'est la somme, pour chaque situation <math>\(\omega\)</math>, du nombre de tirages à une feuille, multiplié par la probabilité de la situation en question. Mais <math>\(\#\{i | T(i)\}\)</math>, le cardinal de l'ensemble des indices <math>\(i\)</math> qui vérifient la condition <math>\(T(i)\)</math>, c'est égal à la somme, pour chaque <math>\(i\)</math>, de 1 si <math>\(T(i)\)</math> est vraie ou 0 sinon, ce qu'on note: <math>\(\sum_i 1(T(i))\)</math> (en réalité c'est 𝟙, un 1 double-barre, mais ça ne plaît pas aux balises math on dirait). Donc l'espérance précédente est égale à:

<math>\(\sum_{\omega \in \Omega} (\sum_{i} 1(X_i(\omega) = 1)) * P(\omega)\)</math>

C'est là que la magie s'opère, on développe, on inverse les deux sommes (ce n'est pas toujours possible mais on agite les bras en espérant que ça soit le cas ici), et on obtient:

<math>\(\sum_{i} (\sum_{\omega \in \Omega} 1(X_i(\omega) = 1) * P(\omega))\)</math>

Mais, de façon générale, <math>\(\sum_{\omega \in \Omega} 1(T(\omega)) * P(\omega)\)</math>, c'est la somme de probabilités de tous les événements <math>\(\omega\)</math> qui vérifient le test aléatoire <math>\(T\)</math>, autrement dit c'est la probabilité globale de <math>\(T\)</math>. Donc la formule est égale à

<math>\(\sum_{i} P(X_i = 1)\)</math>

Autrement dit, l'espérance du nombre de tirages à une feuille est bien égale à la somme des probabilités que chaque tirage ait une feuille.

Je m'excuse d'avance si cette preuve est trop compliquée ou trop technique. Je n'ai presque jamais fait de probabilités, et c'était il y a plusieurs années, donc je ne sais plus trop comment formuler ça de façon vraiment accessible.

Ceci dit, le problème de ta méthode est qu'il y a un très grand nombre de possibilités à considérer. Je me demander s'il ne serait pas plus efficace de simplement faire beaucoup de tirages aléatoires, et de prendre la moyenne du résultat. Combien de tirages faudrait-il pour converger avec une précision suffisante ? C'est une bonne question.

Edit: je n'avais pas vu le message de nabucos, qui part dans une direction tout à fait différente. Tant pis.

Anonyme

3 août 2011 à 14:37:00

reBonjour,
yoch

Citation

Chez moi, je trouve 18 possibilités à l’étape 13 (contre 12 possibilités chez toi), ce qui correspond bien à la somme de

Cette première remarque montre qu'il y a une confusion sur ma notation
E13 n'a rien à voir avec l'étape 13 c'est la deuxième étape!

Voilà plus clairement comment j'ai noté mes matrices :
E15 =(1,1,1,1) est la première étape qui correspond à la ligne 2 de ton extrait de code . Pourquoi j'ai noté 15...Parce que j'ai raisonné en "unité de base A5" au départ 1A2+1A3+1A4+1A5 cela fait 15 unités A5et on enlève un A5 à chaque étape d'où l'indice décroissant.

Donc E14 ou E13, ce ne sont pas les possibilités de la 14ème ou de la 13ème étape mais celle de la seconde et troisième ( à chaque fois j'enlève une unité A 5 et mes matrices calculent grâce à M les nouvelles répartitions possibles.)
Prenons E14 les quatre ligne correspondent aux 4 situations possibles au deuxième tour. On les retrouvent d'ailleurs chez toi dans le désordre: E15, c'est ta ligne 2, E14,1 ta ligne 3, E14,2 ta 10 ,E14, ta ligne 16 et E14, 4 ta ligne 21 !

De même les 12 lignes de ma matrice E13 correspondent aux 12 possibilités du seul second tour , dont on retrouve certaines dans ta liste (...je n'ai pas poursuivi la comparaison exhaustive)
Pour E12,3ème tour il y aurait entre 30 et quarante situations ainsi de suite avec une croissance en progression géométrique comme indiqué dans le premier post..

Ton principe peut être bon mais réalisé trés partiellement et dans un ordre pas trés logique qui ne permet pas, je pense, le systématisme ,tu oublies donc de ce fait beaucoup de situations possibles,enfin je crois.
En final jusqu'à la dernière étape E1 il y a des millions de situations à idenfier par l'algorithme.
Ce que je propose est lourd mais mathématiquement facile et donne normalement un résultat totalement exhaustif

yoch

3 août 2011 à 17:44:48

Citation : nabucos

Citation

Chez moi, je trouve 18 possibilités à l’étape 13 (contre 12 possibilités chez toi), ce qui correspond bien à la somme de
Cette première remarque montre qu'il y a une confusion sur ma notation
E13 n'a rien à voir avec l'étape 13 c'est la deuxième étape!

Voilà plus clairement comment j'ai noté mes matrices :
E15 =(1,1,1,1) est la première étape qui correspond à la ligne 2 de ton extrait de code . Pourquoi j'ai noté 15...Parce que j'ai raisonné en "unité de base A5" au départ 1A2+1A3+1A4+1A5 cela fait 15 unités A5et on enlève un A5 à chaque étape d'où l'indice décroissant.

Donc E14 ou E13, ce ne sont pas les possibilités de la 14ème ou de la 13ème étape mais celle de la seconde et troisième ( à chaque fois j'enlève une unité A 5 et mes matrices calculent grâce à M les nouvelles répartitions possibles.)
Prenons E14 les quatre ligne correspondent aux 4 situations possibles au deuxième tour. On les retrouvent d'ailleurs chez toi dans le désordre: E15, c'est ta ligne 2, E14,1 ta ligne 3, E14,2 ta 10 ,E14, ta ligne 16 et E14, 4 ta ligne 21 !
[...]

Oui, désolé, en fait j'avais très bien compris ta notation, mais je l'ai très maladroitement reprise, d’où ma formulation stupide. Mille excuses.

Alors, clairement, à la deuxième étape, je trouve 18 possibilités là ou tu n'en trouve que 12. Et je pense que ton système est incorrect, je m'auto-cite :

Citation

Ta technique permet de connaitre le nombre de configurations à une étape donnée, pas leur fréquence (une même configuration pouvant être obtenue de diverses manières, je prends un exemple, pour la première ligne de <math>\(\[E_{[14,4]\)</math> tu ne comptabilise que 4 possibilités, alors que l'enveloppe contient 6 feuilles).

__________

@ bluestorm : Merci d'avoir répondu !

Citation : bluestorm

Il me semble que la façon de faire est correcte, et que le bug doit se situer plutôt dans tes algorithmes de calcul du nombre d'enveloppe possible et cie.

Ce n'est pas complètement évident que l'espérance du nombre de tirages vérifiant un critère est égale à la somme des probabilités, pour chaque tirage, qu'il vérifie ce critère. Mais c'est vrai.
[...]
Je m'excuse d'avance si cette preuve est trop compliquée ou trop technique. Je n'ai presque jamais fait de probabilités, et c'était il y a plusieurs années, donc je ne sais plus trop comment formuler ça de façon vraiment accessible.

J'ai essayé (vraiment) de comprendre, mais j'avoue que c'est trop technique pour moi. Tu n'as absolument pas de quoi t'excuser, il me semble

. Je compte bien relire encore, mais en attendant :

Au final, tu es d'accord que la methode que je décris en haut devrait donner le bon résultat. Voici mon code naïf, bien sûr il ne permet pas de résoudre le problème en temps raisonnable, mais je voudrais savoir ce que tu en penses :

def cut_in_half(sheet):
    cut = {'a1':('a2','a3','a4','a5'), 'a2':('a3','a4','a5'), 'a3':('a4','a5'), 'a4':('a5',), 'a5':()}
    return cut[sheet]

# initialise les compteurs
l = [[0,0] for i in range(16)]

def fn(envelope, numBatch):
    if len(envelope) == 0: return

    l[numBatch][0] += 1
    if len(envelope) == 1:
        l[numBatch][1] += 1

    for i in range(len(envelope)):
        sheet = envelope[i]
        fn(envelope[:i] + cut_in_half(sheet) + envelope[i+1:], numBatch + 1)

fn(('a2',), 0)
# affiche les compteurs
print(l)

Citation : bluestorm

Ceci dit, le problème de ta méthode est qu'il y a un très grand nombre de possibilités à considérer.

Là dessus, j'ai une astuce qui semble très bien fonctionner, les résultats correspondent au code naïf ci-dessus pour de petits échantillons, mais pour l'exo en question, la réponse est fausse. Je ne sais que penser...

Citation : bluestorm

Je me demander s'il ne serait pas plus efficace de simplement faire beaucoup de tirages aléatoires, et de prendre la moyenne du résultat. Combien de tirages faudrait-il pour converger avec une précision suffisante ? C'est une bonne question.

Un Monte-Carlo, en somme ? Je vais essayer de l'utiliser pour voir si j'obtiens des résultats proches de ceux de mon code actuel ou non.

EDIT : Bon, le code basé sur Monte Carlo donne un résultat très proche de la bonne solution pour une feuille A1 (et 100000 tirages), et ne donne pas le même résultat que mon code naïf sur une feuille A2. Je vais une ultime fois tenter de comprendre ce qui ne va pas...

bluestorm

3 août 2011 à 18:06:57

J'ai l'impression que le code est correct, et que les résultats sont bons.

Tirer au hasard pour approximer une espérance ne mérite pas vraiment le nom de "Monte-Carlo". Il s'agit d'une propriété de base de l'espérance : c'est la valeur moyenne d'une variable aléatoire, donc si on fait des tirages au hasard et qu'on fait la moyenne, on tend vers l'espérance (théorème des grands nombres).

Anonyme

3 août 2011 à 18:38:09

Bonsoir,
C'est ta façon faire et de comptabiliser qui différe de la mienne.
Mais aprés la deuxième étape , j'ai aussi 18 possibilités!
Dans ma façon d'écrire, il faut additionner :
1 A1 + 1E15+ 4 E14 + 12 E13= 18

Prends la peine de vérifier comme je l'ai fait, je retrouve strictement mes 18 configurations parmi les tiennes dans un ordre différent!
Ce que je fais est donc juste je crois ...et trés facile à programmer.
J'essais de le faire sous Scilab ...par amusement.
J'ai juste un problème de capacité de stockage à régler avec le portable pas terrible que j'utilise, car à la 15 ème étape ça commence à devenir gros si on veut tout stocker!
edit
par contre je ne comprends pas cette phrase

Citation

tu ne comptabilise que 4 possibilités, alors que l'enveloppe contient 6 feuilles).

cela n'a rien a voir, toutes les autres possibilités apparaissent au fur et à mesure de la progression du décompte!

bluestorm

3 août 2011 à 18:41:19

yoch > en supposant que ton algo est bon, je pense que tu pourrais écrire un algorithme plus efficace (tu l'as peut-être déjà fait) qui donne le même résultat : quel est l'ensemble des configurations différentes à l'étape N, et combien de fois chaque configuration apparaît-elle ? Tu as écrit un tutoriel à ce sujet :-'

yoch

3 août 2011 à 19:01:16

Citation : bluestorm

J'ai l'impression que le code est correct, et que les résultats sont bons.

Non, comme mentionné dans mon edit ci-dessus, les résultats sont incorrects (0.36 contre 0.55 avec "monte-carlo", avec une feuille A2 au départ).

Il me semble que je commence à entrevoir pourquoi : le nombre de feuilles dans l'enveloppe à chaque étape est variable, et ça doit créer un déséquilibre dans le décompte. Non ?

Citation : nabucos

Bonsoir,
C'est ta façon faire et de comptabiliser qui différe de la mienne.
Mais aprés la deuxième étape , j'ai aussi 18 possibilités!
Dans ma façon d'écrire, il faut additionner :
1 A1 + 1E15+ 4 E14 + 12 E13= 18

OK, mea culpa, j'avais mal compris.
Non, mal lu : si je compte comme ça, j'en ai 24 (1 + 1 + 4 + 18).

Citation : bluestorm

yoch > en supposant que ton algo est bon, je pense que tu pourrais écrire un algorithme plus efficace (tu l'as peut-être déjà fait) qui donne le même résultat : quel est l'ensemble des configurations différentes à l'étape N, et combien de fois chaque configuration apparaît-elle ? Tu as écrit un tutoriel à ce sujet :-'

Oui, tu m'as percé à jour

. C'est exactement ce que j'ai fait.

bluestorm

3 août 2011 à 19:27:52

En fait je me suis amusé à faire ça aussi, et j'obtiens le même résultat que toi. Pour (1,16) c'est instantané mais ça n'est pas le résultat attendu. Donc soit j'ai mal lu ton énoncé, soit tu l'as mal écrit :pirate:

schadocalex

3 août 2011 à 20:20:44

Je pense que l'algo est faux (ou la compréhension de l'énoncé, je ne sais pas), même si je n'ai compris que vaguement l'énoncé, pourquoi y aurait-il plusieurs enveloppes par job qui n'ont qu'une seule feuille ?

Ah, et aussi, pourquoi faire le calcul avec A1 ? Puisque le premier job ne compte pas et on ne peut se retrouver avec un autre A1 dans la semaine...

EDIT : je n'avais pas vu le code Python (j'ai compris un peu, même si je ne fais pas de Python). Apparemment tu pars de A2, faut tenir aussi compte que le dernier job ne compte pas.

"If debbugging is the process of removing bugs, then programming must be the process of putting them in." (Edsger Dijkstra)

yoch

3 août 2011 à 20:29:47

Citation : schadocalex

Je pense que l'algo est faux (ou la compréhension de l'énoncé, je ne sais pas), même si je n'ai compris que vaguement l'énoncé, pourquoi y aurait-il plusieurs enveloppes par job qui n'ont qu'une seule feuille ?

Rien compris... On énumère toutes les possibilités, on est bien d'accord ?

Citation

je n'avais pas vu le code Python (j'ai compris un peu, même si je ne fais pas de Python). Apparemment tu pars de A2, faut tenir aussi compte que le dernier job ne compte pas.

Non, ce code est un bête test, et j'ai mis A2 parce que A1 mettrait beaucoup trop de temps.

schadocalex

3 août 2011 à 20:32:33

Citation : yoch

Non, ce code est un bête test, et j'ai mis A2 parce que A1 mettrait beaucoup trop de temps.

Mais pourquoi calculer à partir du A1 puisque celui-ci ne rentre pas dans les probabilités ? Idem pour le dernier job.

EDIT : rien dit.

"If debbugging is the process of removing bugs, then programming must be the process of putting them in." (Edsger Dijkstra)

yoch

3 août 2011 à 20:42:48

Citation : schadocalex

Mais pourquoi calculer à partir du A1 puisque celui-ci ne rentre pas dans les probabilités ? Idem pour le dernier job.

Oui, c'est possible, mais ça ne change pas grand chose au final.

Citation : schadocalex

Le tableau fais 16 de longueur, mais si tu pars de A2, le A2 ne vient-t-il pas se placer dans la case 0, et donc le job 0 ?

Oui, c'est clair, le tableau est prévu pour coller au cas ou je passe A1 en argument, avec A2 je n'ai besoin que de 8 cases. Encore une fois, c'est du détail, le code est simplement à titre de test.

bluestorm

3 août 2011 à 20:44:25

yoch > j'ai compris le problème. Tu calcules le nombre, ou l'ensemble des enveloppes à l'étape N. Mais toutes ces enveloppes n'ont pas la même probabilité, pour deux raisons différentes, et nous avions oublié la deuxième:
- certaines enveloppes peuvent venir de deux enveloppes de l'étape N-1 différentes, donc il faut additionner les probabilités (fait)
- quand tu regardes une enveloppe à K feuilles à l'étape N-1, elle génère K enveloppes à l'étape N, mais chacune a seulement une probabilité 1/K d'être choisie !

Il faut donc prendre en compte la "taille" d'une enveloppe dans la probabilité d'obtenir ses enveloppes filles. En corrigeant mon code pour gérer ça, j'ai obtenu le résultat attendu.

schadocalex

3 août 2011 à 20:54:13

Il n'y a qu'une enveloppe... mais le résultat est là, donc peu importe.

"If debbugging is the process of removing bugs, then programming must be the process of putting them in." (Edsger Dijkstra)

yoch

3 août 2011 à 21:08:09

Citation : bluestorm

yoch > j'ai compris le problème. Tu calcules le nombre, ou l'ensemble des enveloppes à l'étape N. Mais toutes ces enveloppes n'ont pas la même probabilité, pour deux raisons différentes, et nous avions oublié la deuxième:
- certaines enveloppes peuvent venir de deux enveloppes de l'étape N-1 différentes, donc il faut additionner les probabilités (fait)
- quand tu regardes une enveloppe à K feuilles à l'étape N-1, elle génère K enveloppes à l'étape N, mais chacune a seulement une probabilité 1/K d'être choisie !

Il faut donc prendre en compte la "taille" d'une enveloppe dans la probabilité d'obtenir ses enveloppes filles. En corrigeant mon code pour gérer ça, j'ai obtenu le résultat attendu.

Exactement ! C'est ce que je soupçonnais ci-dessus, merci de l'avoir confirmé (je n'étais pas certain).

En revanche, je coince un peu pour gérer ça : j'ai essayé, mais ma solution ne marche pas et rend mon code assez affreux. Je crois que je vais y réfléchir plus tard à tête reposée.

Citation : schadocalex

Il n'y a qu'une enveloppe...

On parle d'"enveloppes possibles", c'est bien clair qu'il n'y en a qu'une en réalité...

EDIT :
Voici enfin la solution :

l = [[0,0] for i in range(16)]

def fn(envelope, numBatch, fact):
    if len(envelope) == 0: return
    l[numBatch][0] += fact
    if len(envelope) == 1:
        l[numBatch][1] += fact

    for i, sheet in enumerate(envelope):
        sheet = envelope[i]
        fn(envelope[:i] + cut_in_half(sheet) + envelope[i+1:], numBatch + 1, fact * (1 / len(envelope)))

fn(('a2',), 0, 1)
print(sum([elt[1]/elt[0] for elt in l if elt[0] != 0][1:-1]))

Encore merci bluestorm, c'est la tournure de ta phrase qui m'a fait tilt.

EDIT2 : correction du code

Anonyme

3 août 2011 à 21:41:30

Bonsoir,
à Yoch
laborieusement.. mais je pense enfin avoir compris le pourquoi de l'écart entre nos 2 listes 18/24.
Ton décompte fait apparaitre des configurations identiques qui n'apparaissent pas dans mon calcul, donc je comprends a posteriori ta remarque initiale de ton premier post sur les doublons que je n'avais pas alors saisie.

Je n'ai pas pensé en terme de probabilité mais seulement de configuration .

Ceci étant, je ne pense pas que cela rende caduque le traitement algorithmique suggéré.
Il suffit que dans mes matrices (E) successives, je comptabilise une nouvelle configuration autant de fois que la valeur à laquelle on applique le -1 de la matrice M .
Avec cela, je pense que nos premiers décomptes sont identiques.

(PS pour la bonne forme je ferai un Edit de ma matrice E13 car j'ai fait des erreurs de copie!)

bluestorm

3 août 2011 à 21:44:39

For the record, mon code:

cut = {i:tuple(range(i+1,6)) for i in range(1,6)}

def sort_tuple(tup):
    tmp = list(tup)
    tmp.sort()
    return tuple(tmp)

def compute_probs(start, nb_iter):
    l = [{} for i in range(nb_iter)]
    
    l[0] = {cut[start]: 1}
    for i in range(1,nb_iter):
        for envel, prob in l[i-1].items():
            for j in range(len(envel)):
                new_envel = sort_tuple(envel[:j] + cut[envel[j]] + envel[j+1:])
                if new_envel not in l[i]:
                    l[i][new_envel] = 0
                l[i][new_envel] += prob / len(envel)
    return l

def count(l):
    res = []
    for d in l:
        total = 0
        one_leaf = 0
        for envel, prob in d.items():
            total += prob
            if len(envel) == 1:
                one_leaf += prob
        res.append((total, one_leaf))
    return res

def expectancy(n):
    nb_iter = pow(2,5-n)
    probs = compute_probs(n, nb_iter)
    return sum([one/total for total, one in count(probs)[:nb_iter-2]])