Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
question sur les dénombrements
6 views
Skip to first unread message
pierre
Feb 4, 2012, 2:05:27 PM2/4/12
to
Bonjour,
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 ?
exemple :
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.
y a-t-il une formule mathématique permettant de calculer cela ?
merci
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 ?
exemple :
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.
y a-t-il une formule mathématique permettant de calculer cela ?
merci
pierre
Olivier Miakinen
Feb 6, 2012, 12:02:10 PM2/6/12
to
Bonjour,
Le 04/02/2012 20:05, pierre a écrit :
>
> 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 ?
>
> exemple :
> 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é ?
> 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
Le 04/02/2012 20:05, pierre a écrit :
>
> 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 ?
>
> exemple :
> 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.
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é ?
> y a-t-il une formule mathématique permettant de calculer cela ?
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
Feb 7, 2012, 5:17:11 PM2/7/12
to
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
Feb 8, 2012, 1:32:29 AM2/8/12
to
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
Feb 8, 2012, 3:56:20 AM2/8/12
to
http://99problemsinscala.wordpress.com/2009/04/19/p08-eliminate-consecutive-duplicates-of-list-elements/
--
Cordialement
Jean-Louis Pasturel
Guillaume Tello
Feb 8, 2012, 10:09:53 AM2/8/12
to
Le 08/02/2012 09:56, jlp a écrit :
> 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,
> En Scala par exemple
> http://99problemsinscala.wordpress.com/2009/04/19/p08-eliminate-consecutive-duplicates-of-list-elements/
>
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.
>
>
Ulf Iversen
Feb 9, 2012, 7:04:21 AM2/9/12
to
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
Feb 9, 2012, 7:14:04 AM2/9/12
to
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.
Ulf Iversen
Feb 9, 2012, 8:57:04 AM2/9/12
to
Am Thu, 09 Feb 2012 13:14:04 +0100 schrieb Guillaume Tello:
> Le 09/02/2012 13:04, Ulf Iversen a écrit :
>> Am Wed, 08 Feb 2012 07:32:29 +0100 schrieb Guillaume Tello:
>>
>>> Le 07/02/2012 23:17, pierre a écrit :
>>>> Le 06/02/2012 18:02, Olivier Miakinen a écrit :
>>>>> Bonjour,
>>>>>
>>>>> Le 04/02/2012 20:05, pierre a écrit :
>>>>>>
>>>>>> 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 ?
>>>>>>
>>>>>> exemple :
>>>>>> 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.
>>>
> Le 09/02/2012 13:04, Ulf Iversen a écrit :
>> Am Wed, 08 Feb 2012 07:32:29 +0100 schrieb Guillaume Tello:
>>
>>> Le 07/02/2012 23:17, pierre a écrit :
>>>> Le 06/02/2012 18:02, Olivier Miakinen a écrit :
>>>>> Bonjour,
>>>>>
>>>>> Le 04/02/2012 20:05, pierre a écrit :
>>>>>>
>>>>>> 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 ?
>>>>>>
>>>>>> exemple :
>>>>>> 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.
>>>
>>> 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.
>>
>> 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).
>
> 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.
J'en suis assez sur à cause de la logique de mon algorhytme qui fonction à
>> 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.
>>
>> 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).
>
> 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.
peu près ainsi:
iterer sur tout les possibilité pour la premier lettre (5), puis pour
chaque cas, iterer sur tout les possibilité pour la deuxième lettre et
ainsi de suite, en excluant la lettre qui est egale à la précédente et
celles dont il y en reste plus.
Du reste le chiffre ne me parait pas trop élévé. Si je calcule bien il y
a environ 303 Millions de permutations:
16!/(5!x2!x4!2!x3!)
il n'y aurait donc qu'un vingtième de ces permutations qui comporte pas
de sans doublons consécutifs.
ciao
Ulf
jlp
Feb 9, 2012, 11:42:04 AM2/9/12
to
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
0 new messages