Discussion :

[j.p.mignot]

On dispose de "Nuplets" de bits allant de
{0,0,...,0} à {1,1,...1} N est un entier à prioris quelconque et en pratique allant de 8 à 32.

Ily y a donc 2^N Nuplets différents.

De ces 2^N on souhaite obtenir le cardinal de la sous-famille contenant les Nuplets pour lesquels ont a au moins une fois p bits consécutifs (ou plus)égaux p<=N bien entendu ( en pratique p=6)

Quelqu'un aurrait-il une idée comment on pourrait formuler le résultat sans utiliser un PC et générer le liste complète de Nuplets puis retenir ceux qui sont acceptés (au moins une fois "111111.." ou "000000..")?

On peut décomposer en calculant ce nombre pour les Nuplets contenant STRICTEMENT x bits consécutifs égaux puis sommer pour x=p à N.
si on recherche x bit =1 alors il faut multiplier le résultat final par 2 (on à la symétrie avec x bits=0)

la situation est alors
code (0 et 1 forcés, X code libre)
1111110XXXXXXX h=0 N bits, serie de x bits =1 p<=x<=N
01111110XXXXXX h=1
X01111110XXXXX h=2
..
XXXXXX01111110
XXXXXXX0111111 h=N-x

Nombre de croix à droite ligne h : d = max(0,N-x-h-1)
Nombre de croix à gauche ligne h : g = max(0,h-1)

le nombre de possibilité [pour cette valeur particulière de x et qu'il faudra sommer pour x=p..N] est alors la somme de 2^d * 2^(f(g)) sur l'ensemble des lignes
on a pas 2^g mais 2^f(g) car alors on compterait des doublons comme par exemple:
11111101111110xxxxxxxxxxx
qui serait compté pour h=0 et h=8

C'est là que j'ai un petit problème de formalisme! comment écrire proprement f(g)?

merci por vos réponses!

[Aleph69]

Bonjour,

je n'ai pas compris ce passage :

De ces 2^N on souhaite obtenir le cardinal de la sous-famille contenant les Nuplets pour lesquels ont a au moins une fois p bits consécutifs (ou plus)égaux p<=N bien entendu ( en pratique p=6)

Est-ce qu'on peut avoir plusieurs suites de p bits consécutifs égaux?
Est-ce qu'on peut avoir des suites de q bits consécutifs égaux avec q>p?

[Invité]

Dans la littérature, ce type de problème est appelé "longest run" (plus longue série). En général, c'est formulé en terme de pile ou face : la série la plus longue de pile ou de face quand on joue N fois à pile ou face.

Voici un article, le paragraphe intitulé "fair coin" correspond, je crois, exactement à ton problème.

http://gato-docs.its.txstate.edu/mat...LongestRun.pdf

Francois

[j.p.mignot]

Est-ce qu'on peut avoir plusieurs suites de p bits consécutifs égaux?
Est-ce qu'on peut avoir des suites de q bits consécutifs égaux avec q>p?

Oui.

parmis les 2^N Nuplets on crée une sous-famille (fonction de p bien entendu) pour laquelle retient tous les Nuplets des 2^N de l'original pour lesquels il y a au moins "quelque part" une serie de p bits consécutifs (ce qui n'exlue pas p+1, p+2,..) identiques que se soit une serie de 0 ou 1.
par exemple si N=4 et p=2
l'ensemble de départ est
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1100 1111

le sous ensemble retenu pour p=2 serait
0000
0001
0010
0011
0100
NON 0101
0110
0111
1000
1001
NON 1010
1011
1100
1101
1110
1111

[Alexis.M]

Je ne suis pas sûr que tu aies de solutions miracle. Moi je reprendrais
l'idée que tu développes prenant en compte séparément la première et la dernière ligne.

Pour toutes les autres, je considère que j'ai:
01....10xxx...xxx (1)

Comme la concaténation du motif 011....10 et d'un entier codé en mode binaire. Je peux donc itérer sur cet entier. Tous les autres motifs sont
construictible par permutation circulaire du motif (1)

de 01...10xx....xx à xx...xx01...10.

Donc tu génère toute le monde avec deux boucles imbriquées

Les première et dernière lignse doivent être traiter séparément. Tu peux appliquer le même principe mais sans la permutation circulaire.

J'ai rencontré des choses similaires, quand j'ai travaillé sur les local binary patterns (LBP) et leurs variantes invariantes par rotation et uniformes.

[j.p.mignot]

Je ne suis pas sûr que tu aies de solutions miracle

C'est un peu ce que je redoute!

J'ai des algorithmes récurcifs qui fonctionnent. L'idée serait d'essayer de formuler de façon 'littérale directe' le résultat. Il n'est pas non plus question de probabilité qui correpondrait à la solution 'limite' si N ==> infini. Ici le résultat doit tenir compte des "effets de bord" car p n'est pas infiniment petit devant N. Tant que p > N/2 cela est facile car dans la matrice que j'ai esquisé ci-dessus, ni les parties left ni les partie righr ne peuvent ré-introduire une nouvelle série de p éléments. Après cela est plus délicat pour formuler le décompte sans un algorithme récurcif dont il est difficile de donner le résultat uniquement en le lisant sur le papier.

[Invité]

J'ai des algorithmes récurcifs qui fonctionnent.

Si tu as la récurrence, quelque chose comme:

F(n,p)= 2 ( F(n-1,p-1) + F(n-2,p-1) + ... F(n-p+1,p-1) )

(F(n,p) nombre de chaines de longueur n n'ayant pas de suites de plus de p valeurs, il faudrait vérifier via l'article cité plus haut). F(n,p) est bien plus facile à calculer de cette façon que par énumération. Et tu disposeras de formules fermées pour certaines valeurs de p (par exemple, pour p=3 tu dois avoir quelque chose de lié aux suites de Fibonacci)

Francois

[Aleph69]

Bonsoir,

ce serait bien que tu envoies ton algorithme de dénombrement car cela peut donner des idées pour faire un raisonnement par récurrence. Sinon, est-ce que tu as essayé de raisonner en partant de la séquence de N bits consécutifs? Par exemple, en partant de 11111? Ici, il n'y a aucune séquence de p bits sauf pour p=N=5 où il y en une. Maintenant, introduisons un 0. Il y a cinq emplacements possibles mais par symétrie tu ne peux en considérer que 3 :
11110
11101
11011
La première définit une seule séquence de 4 bits égaux. La seconde une seule séquence de 3 bits égaux. La dernière deux séquences de 2 bits égaux. Ensuite, tu introduis deux 0 et ainsi de suite. Je ne sais pas si l'approche aboutit à quelque chose mais on ne sait jamais. Je me pencherai dessus demain.

Cette approche revient plus ou moins à se poser la question : avec q uns et N-q zéros, combien puis-je faire de séquences consécutives de p uns pour p variant de 1 à q?

Il y a un autre aspect qui peut-être exploité. L'ensemble S(N,p) des séquences de p bits consécutifs contient toutes les séquences S(N,q) de q bits consécutifs pour q>=p. En d'autres termes, S(N,p) doit s'écrire comme la réunion des S(N,q) pour q>p, elle-même réunie avec l'ensemble des séquences d'exactement p bits (pas p+1, ni p+2, etc). En tirant parti de cela, et en procédant par récurrence, je pense que tu peux ramener ton problème au dénombrement des séquences d'exactement p bits pour p variant de 1 à N. Comme tu l'as remarqué, dans le cas p>N/2, c'est trivial. Pour p<=N/2, il faut "casser" la séquence pour qu'elle ne contienne pas plus de p bits (l'entourer de 0 si c'est une séquence de 1) et faire en sorte de ne pas créer d'autres séquences de p bits.

Ce sont quelques idées en vrac, je réfléchirai à tout cela demain.

Envoie ton algorithme, ça peut vraiment aider.

[pseudocode]

De ces 2^N on souhaite obtenir le cardinal de la sous-famille contenant les Nuplets pour lesquels ont a au moins une fois p bits consécutifs (ou plus)égaux p<=N bien entendu ( en pratique p=6)

Tu as une chaine de 'p' bits (tous à zéro ou tous à un), et tu cherches à compléter cette chaine (à gauche et/ou à droite) pour avoir une chaine de N bits ?

chaine = {a bits}+{p bits}+{b bits}
avec a+p+b= N

c'est ca ?

[Invité]

Tu as une chaine de 'p' bits (tous à zéro ou tous à un), et tu cherches à compléter cette chaine (à gauche et/ou à droite) pour avoir une chaine de N bits ?

chaine = {a bits}+{p bits}+{b bits}
avec a+p+b= N

c'est ca ?

Si tu concatènes par les deux bouts, tu vas avoir des double comptes.

Par exemple, pour N=7 et p=3, tu as

1111000 = "" + 111 + 1000 = 1 + 111 + 000 = 1111 + 000 + ""
non?

Francois

[j.p.mignot]

Exact! Les doublons c'est bien là le problème que j'avais noté

est alors la somme de 2^d * 2^(f(g)) sur l'ensemble des lignes
on a pas 2^g mais 2^f(g) car alors on compterait des doublons

dans mon post d'origine. Sans cela el problème serait évident...

[j.p.mignot]

Tu as une chaine de 'p' bits (tous à zéro ou tous à un), et tu cherches à compléter cette chaine (à gauche et/ou à droite) pour avoir une chaine de N bits ?

chaine = {a bits}+{p bits}+{b bits}
avec a+p+b= N

Pas tout à fait...

On a N & p donnés ( p<=N)

On cherche la famille des Nuplets de bits qui ont la forme

a bits + x bits + b bits

et qui respectent les propriétés suivantes:

1- a+x+b=N
2- N>= x >=p ( mais x n'est pas limité à p)
3- Tous les bits de x sont égaux soit 1 soit 0 (sans considération sur ceux de a ou b)

Le but est alors d'obtenir le Cardinal de cet ensemble = f(N, p) et finalement, en le divisant par 2^N, obtenir la probabilité d'une telle propriété dans la famille de 2^N Nuplets {(0...0),...,(1...1)} d'origine

Etablir cette liste en générant les 2^N Nuplets et en les testant est long et ne donne pas les tendances comme une équation le ferait.
Etablir cette liste par récurance est aussi possible. Le calcul est plus court mais là encore pas d'équation permettant de facilement voir les tendances et limites.

On cherche à chiffrer ce cardinal via une équation aussi simple que possible de préférence pour povoir aisément donner un résultat et l'évolution de ce résultat si on change N ou p.

[Invité]

hello,

On peut essayer de construire le contraire (C={aucun p bits consécutifs}) puis de prendre le contraire 2^N-|C|

pour ca on commence notre série avec (supposons p=2) les deux premiers bits
00
01
10
11

On note f, la fonction qui au couple <a,b> associe l'ensemble des couples <b,c> tels que <a,b,c> ne soient pas tous égaux.
f(00)={01}
f(01)={11,10}
f(10)={01,00}
f(11)={00}

On peut représenter cette représentation par une matrice d'adjacenceM:

Code :

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

1
2
3
4
5
6
00 01  10 11
____________|
0   1   0  0|00
0   0   1  1|01
1   1   0  0|10
0   0   1  0|11

On a donc le nombre de chemins depuis un noeud a un autre.

Il reste à élever M à la puissance N-p (à l'indice près...)

Le problème reste à trouver pour p quelconque, et bien sûr expliciter M^{N-p}

[Invité]

Pas tout à fait...

Je crois que pseudocode avait compris... Ce qu'il proposait c'est une construction permettant de trouver la récurrence. D'ailleurs, sa solution fonctionne si on la précise un peu, en imposant à la chaine de gauche de n'avoir aucune suite de p bits identiques et de ne pas finir par le bit de la séquence. On a alors une construction de type

A (k bits finissant par zéro, sans séquence de longueur p)
1....1 (p fois)
B (n-p-k bits quelconques)



Je peux me tromper, mais j'ai l'impression que tu ne connais pas du tout la méthode habituelle pour résoudre ce type de problème. Tu devrais VRAIMENT lire l'article donné en référence un peu plus haut (qui résoud entièrement ton problème, approximations de la fonction finale comprises).

Francois

[pseudocode]

Si tu concatènes par les deux bouts, tu vas avoir des double comptes.

Par exemple, pour N=7 et p=3, tu as

1111000 = "" + 111 + 1000 = 1 + 111 + 000 = 1111 + 000 + ""
non?

pour N=7 et p=3, ne cherche-t-on pas les chaines:

(4 bits) + "111" + ""
(3 bits) + "111" + (1 bit)
(2 bits) + "111" + (2 bits)
(1 bit) + "111" + (3 bits)
"" + "111" + (4 bits)

C'est à dire qu'on cherche a compléter "111" par toutes les chaines de 4 bits (2^4) splitées en 2 parties (1+N-p):

Cardinal = 2^(N-p) * (1+N-P)

?

[Invité]

pour N=7 et p=3, ne cherche-t-on pas les chaines:

(4 bits) + "111" + ""
(3 bits) + "111" + (1 bit)
(2 bits) + "111" + (2 bits)
(1 bit) + "111" + (3 bits)
"" + "111" + (4 bits)

C'est à dire qu'on cherche a compléter "111" par toutes les chaines de 4 bits (2^4) splitées en 2 parties (1+N-p):

Cardinal = 2^(N-p) * (1+N-P)

En fait, non, ce qu'il veut, c'est le nombre de chaines (sur les 2^N) ayant des séquences de 0 ou 1 de longueur p dedans. Dans ton exemple, si les sous chaines gauche ET droite de l'expression sont quelconques, tu vas compter plusieurs fois la même (en fait, autant de fois qu'il y aura de 111 dedans).

Mais, comme je le disais dans le post précédent, on peut adapter ta méthode pour la faire marcher dans ce cas, en imposant à la chaine "111" d'être la première du nombre, donc en contraignant la sous chaine de gauche, ou de droite.

Francois

[Invité]

Tu devrais VRAIMENT lire l'article donné en référence un peu plus haut

Il aura fallu les caps lock pour que je remarque l'intitule fair coin...

effectivement, c'est joli, pas cacule le resultat final mais il se calcule bien

[pseudocode]

En fait, non, ce qu'il veut, c'est le nombre de chaines (sur les 2^N) ayant des séquences de 0 ou 1 de longueur p dedans. Dans ton exemple, si les sous chaines gauche ET droite de l'expression sont quelconques, tu vas compter plusieurs fois la même (en fait, autant de fois qu'il y aura de 111 dedans).

Ah oui, ok.

Retour de vacances, j'ai un peu de mal.

[j.p.mignot]

Je viens d'étudier l'article référencé par fcharton/François

Je m'excuse de n'avoir eu le temps de le faire plus tôt car effectivement tout y est.

Merci de vos collaborations respectives.