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

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

C'est quoi une séquence ? Car pour moi la séquence, ce n'est pas 44 mais 4 ici.

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.

Oui mais c'est une séquence maximal que l'on cherche non ? La spécification n'est pas clair là.

Pour moi une séquence, c'est au moins deux chiffres d'affilés, donc 4 ne vas pas

Tu veux donc trouver un nombre de deux chiffres qui apparaît le plus dans ton nombre ?

yep

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.

La ligne 5 suppose que tu ne cherches que des séquences du type XX. Or il ne me semble pas que ce soit imposé. Mais là encore c'est flou.

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 !

D'ailleurs, si tu souhaites un bon exercice supplémentaire, il existe un algorithme plus évolué pour compter le nombre d'occurrence d'un mot : https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm .

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

Hélas, je n'utilise pas Python :/

Hélas en effet