question sur les dénombrements

Bonjour,

Post by pierre
j'ai un exo que je ne sais pas comment résoudre.
j'ai une liste de lettres, par exemple : AAAAABBCCCCDDEEE
comment peut-on faire le dénombrement des chaînes ne comportant pas de
doublons consécutifs ?
ABECABEACEDACEACDE
on n'a jamais de AA, ni de BB, ni de CC, ni de DD ni de EE dans la
chaîne, et il y a 5 A, 2 B, 4 C, 2 D et 3 E, comme dans la liste de lettres.

Eh bien ça ne me semble pas facile.

Histoire que les spécialistes te répondent de façon adaptée, dans quelle
classe (ou à quel niveau d'études) cet exo t'a-t-il été proposé ?

Post by pierre
y a-t-il une formule mathématique permettant de calculer cela ?

Je ne le pense pas, mais il est très possible que je me trompe. Si on
te demandait juste le nombre de façons de mettre cinq A dans seize
cases sans qu'ils se touchent, ce serait facile : la réponse est la
même que pour cinq A dans douze cases (16 - 5 + 1) avec la possibilité
qu'ils soient consécutifs. Mais avec les autres lettres je ne sais pas
répondre.

Cordialement,

--
Olivier Miakinen

pierre

2012-02-07 22:17:11 UTC

Post by pierre
Bonjour,

Eh bien ça ne me semble pas facile.
Histoire que les spécialistes te répondent de façon adaptée, dans quelle
classe (ou à quel niveau d'études) cet exo t'a-t-il été proposé ?

Post by pierre
y a-t-il une formule mathématique permettant de calculer cela ?

je ne suis plus étudiant depuis longtemps, c'était juste pour faire un
algo qui décompte les possibilités ; de temps en temps je me donne un
petit exo à résoudre; le précédent avait été sans conditions, et ça a
été facile; là, j'ai voulu un peu compliquer les choses, mais vu ta
réponse, je crois que j'ai choisi quelque chose de très compliqué, alors
que ça paraît simple...

je pense que ça doit valoir le coup de faire un peu de recherche dessus,
non ?

je vais me pencher un peu plus sur la chose...

en tout cas, merci de ta réponse

pierre

Guillaume Tello

2012-02-08 06:32:29 UTC

Post by pierre
Bonjour,

Eh bien ça ne me semble pas facile.
Histoire que les spécialistes te répondent de façon adaptée, dans quelle
classe (ou à quel niveau d'études) cet exo t'a-t-il été proposé ?

Post by pierre
y a-t-il une formule mathématique permettant de calculer cela ?

je ne suis plus étudiant depuis longtemps, c'était juste pour faire un
algo qui décompte les possibilités ;

En programmant ça devrait aller non? On peut simuler ça. Meme avec un
algorithme un peu bourrin qui cherche toutes les positions et qui
regarde au final si deux lettres égales se touchent (un NON) ou si elles
sont toutes séparées (un OUI).
Avec la rapidité des machines actuelles, tu devrais avoir la réponse
assez vite.

Guillaume.

jlp

2012-02-08 08:56:20 UTC

Post by pierre
Bonjour,

Eh bien ça ne me semble pas facile.
Histoire que les spécialistes te répondent de façon adaptée, dans quelle
classe (ou à quel niveau d'études) cet exo t'a-t-il été proposé ?

Post by pierre
y a-t-il une formule mathématique permettant de calculer cela ?

je ne suis plus étudiant depuis longtemps, c'était juste pour faire un
algo qui décompte les possibilités ;

En Scala par exemple
http://99problemsinscala.wordpress.com/2009/04/19/p08-eliminate-consecutive-duplicates-of-list-elements/

--
Cordialement
Jean-Louis Pasturel

Guillaume Tello

2012-02-08 15:09:53 UTC

Post by jlp
En Scala par exemple
http://99problemsinscala.wordpress.com/2009/04/19/p08-eliminate-consecutive-duplicates-of-list-elements/

J'avoue ma nullité en Scala et tout autre langage du genre (Lisp,
Prolog..) mais la routine proposée, si je la capte bien, ne permet que
de proposer une solution dans la quelle il n'y a pas de lettres
consécutives égales.

Est-ce qu'elle pourrait aussi parcourir l'ensemble des possibles et
compter les bonnes solutions? Donner une probabilité par exemple.

Guillaume.

jlp

2012-02-09 16:42:04 UTC

Post by jlp
En Scala par exemple
http://99problemsinscala.wordpress.com/2009/04/19/p08-eliminate-consecutive-duplicates-of-list-elements/

J'avoue ma nullité en Scala et tout autre langage du genre (Lisp,
Prolog..) mais la routine proposée, si je la capte bien, ne permet que
de proposer une solution dans la quelle il n'y a pas de lettres
consécutives égales.
Est-ce qu'elle pourrait aussi parcourir l'ensemble des possibles et
compter les bonnes solutions? Donner une probabilité par exemple.
Guillaume.

Excusez-moi, j'avoue avoir mal lu le problème posé
Effectivement, la fonction extrait, à partir d'une suite de caractères
*fourni*, la suite de caractères sans doublon consécutif
Ce qui n'est pas la solution au problème initial

--
Cordialement
Jean-Louis Pasturel

Ulf Iversen

2012-02-09 12:04:21 UTC

Post by pierre
Bonjour,

Post by pierre
j'ai un exo que je ne sais pas comment résoudre.
j'ai une liste de lettres, par exemple : AAAAABBCCCCDDEEE
comment peut-on faire le dénombrement des chaînes ne comportant pas
de doublons consécutifs ?
ABECABEACEDACEACDE
on n'a jamais de AA, ni de BB, ni de CC, ni de DD ni de EE dans la
chaîne, et il y a 5 A, 2 B, 4 C, 2 D et 3 E, comme dans la liste de lettres.

Eh bien ça ne me semble pas facile.
Histoire que les spécialistes te répondent de façon adaptée, dans
quelle classe (ou à quel niveau d'études) cet exo t'a-t-il été proposé
?

Post by pierre
y a-t-il une formule mathématique permettant de calculer cela ?

je ne suis plus étudiant depuis longtemps, c'était juste pour faire un
algo qui décompte les possibilités ;

réponse

Post by Guillaume Tello
assez vite.
Guillaume.

J'ai essayé de faire ça. Pour l'exemple donné, j'arrive a 14547516
solutions. Bon je ne les ai pas vérifiés tous, mais le calcul me parait
correct (J'ai les solutions en format .txt, si quelqu'un veut y regarder
de plus près).

Mais, avec ça, le problème n'est pas vraiment résolut. D'un côté, savoir
produire tous les chaines possible, c'est pas tout à fait la même chose
que savoir calculer leur nombre. Et puis le temps que l'ordinateur y met,
doit croitre de manière à peu près exponentiel avec le nombre des
elements. En ajoutant quelque lettre on arrive donc assez vite à un point
ou l'ordinateur ne sert plus à rien.

Ulf
Les maths en français c'est nouveau pour moi, n'hésitez pas à me corriger.

Guillaume Tello

2012-02-09 12:14:04 UTC

Post by pierre
Bonjour,

Post by pierre
j'ai un exo que je ne sais pas comment résoudre.
j'ai une liste de lettres, par exemple : AAAAABBCCCCDDEEE
comment peut-on faire le dénombrement des chaînes ne comportant pas
de doublons consécutifs ?
ABECABEACEDACEACDE
on n'a jamais de AA, ni de BB, ni de CC, ni de DD ni de EE dans la
chaîne, et il y a 5 A, 2 B, 4 C, 2 D et 3 E, comme dans la liste de lettres.

Eh bien ça ne me semble pas facile.
Histoire que les spécialistes te répondent de façon adaptée, dans
quelle classe (ou à quel niveau d'études) cet exo t'a-t-il été proposé
?

Post by pierre
y a-t-il une formule mathématique permettant de calculer cela ?

je ne suis plus étudiant depuis longtemps, c'était juste pour faire un
algo qui décompte les possibilités ;

En programmant ça devrait aller non? On peut simuler ça. Meme

avec un

Post by Guillaume Tello
algorithme un peu bourrin qui cherche toutes les positions et qui
regarde au final si deux lettres égales se touchent (un NON) ou si elles
sont toutes séparées (un OUI).
Avec la rapidité des machines actuelles, tu devrais avoir la

réponse

Post by Guillaume Tello
assez vite.
Guillaume.

Ca me semble beaucoup (à vue d'oeil).
As tu tenu compte des doubles? Par exemple A1 B A2 c'est pareil que A2
B A1 puisque tous les A se valent.

Guillaume.

Post by Guillaume Tello
Mais, avec ça, le problème n'est pas vraiment résolut. D'un côté, savoir
produire tous les chaines possible, c'est pas tout à fait la même chose
que savoir calculer leur nombre. Et puis le temps que l'ordinateur y met,
doit croitre de manière à peu près exponentiel avec le nombre des
elements. En ajoutant quelque lettre on arrive donc assez vite à un point
ou l'ordinateur ne sert plus à rien.
Ulf
Les maths en français c'est nouveau pour moi, n'hésitez pas à me corriger.

Ulf Iversen

2012-02-09 13:57:04 UTC