Trouver la séquence la plus présente dans une suite de chiffres

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour :)
Existe t'il un algorithme permettant de trouver la séquence la plus présente dans une suite de chiffres ?

Exemple : j'ai cette suite de chiffres : 41544515846117631449611544

l'algorithme devra me retourner 44 ;) Une idée ? cordialement

Édité par Coyote

(ಠ_ಠ) visite Drozor

+0 -0

Déjà, on remarque que si on a $n$ séquences de 3 chiffres (1234123512361237), on en a au moins $n$ de 2 chiffres (1234123512361237). Du coup, on peut directement chercher les séquences de deux (taille minimale d'une séquence) chiffres.

Pour la suite, aucune idée pour l'instant.

+0 -0

est-ce que 444 compte pour 2 séquences 44 du coup ? à priori oui ? Ca donnerait ce genre d'algorithme ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def chercher_plus_presente_sequence(txt):
    sequences = {}
    best = None
    for i in range(len(txt)-1):
        if txt[i] == txt[i+1]:
            if not txt[i] in sequences:
                sequences[txt[i]] = 1
            else:
                sequences[txt[i]] += 1
            if best is None or sequences[txt[i]] > sequences[best]:
                 best = txt[i]
    return best

EDIT : mon voisin du dessous a parfaitement raison, mais la démarche doit y être, il suffit de stocker les sequences à deux caractères en clés plutot qu'un seul, et sa remarque au début du sujet nous permet de ne pas chercher plus que ça, sauf si tu cherches la plus grande chaine parmi les séquences de fréquence maximale.

Édité par unidan

+0 -0
Auteur du sujet

Oui :)
en m'inspirant de ton algo, j'ai pensé a ça (en VB.net):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
            For hg As Integer = 1 To 10 'pour voir les 10 premiers


                Dim arr(99) As Integer 'vu qu'on est sur deux chiffres max, pas besoin d'aller plus haut^^
                For n As Integer = 10 To 99 Step +1
                    arr(n) = CompterMot(i, n)
                Next


                Dim max As Integer = 0
                Dim nb As Integer = 0
                For n As Integer = 10 To 99 Step +1
                    If nb < arr(n) Then
                        nb = arr(n)
                         max = n
                    End If
                Next

                i = Replace(i, max, "")
                t = Replace(t, max, le(hg - 1))
                TextBox1.Text = TextBox1.Text & max & " : " & nb & vbNewLine

            Next

La fonction CompterMot retourne le nombre d'occurence d'une chaine dans un texte :

1
2
3
4
    Public Function CompterMot(strPhrase, strMot) As Integer
        Dim strTab = Split(strPhrase, strMot)
        CompterMot = UBound(strTab)
    End Function

et après en modifiant les valeurs des boucles, on peut chercher que des nombres a 3 chiffres :)

Et ça marche super :) Merci de ton aide !

Édité par Aze

(ಠ_ಠ) visite Drozor

+0 -0

Je me suis dis que c'était un travail pour itertools, je ne me suis pas trompé, j'ai trouvé la fonction groupby très sympa…

1
2
3
4
5
6
7
8
from itertools import groupby

s = "41544515846117631449611544"

res = [list(g) for k, g in groupby(s)]
res = sorted(res, key=len, reverse=True)
for seq in res:
    print(''.join(seq))

Sortie

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
11
44
4
1
5
5
1
5
8
4
6
7
6
3
1
9
6
5

Ce qui donne au final ce code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from itertools import groupby

s = "41544515846117631449611544"

res = [list(g) for k, g in groupby(s)]
res = sorted(res, key=len, reverse=True)
resultat = []
for seq in res:
    if len(seq) < len(res[0]):
        break
    value = ''.join(seq)
    if value not in resultat:
        resultat.append(value)

resultat = sorted(resultat, key=s.count, reverse=True)
print(resultat[0]) # 44

Pour 1 Million de caractères, un temps de 1,4 seconde c'est pas si mal :)

Édité par fred1599

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte