Trouver séquence incrémentale de n nombres

Hello,
le titre est peut-être pas très explicite alors voici des explications.
Soit une liste de 10 nombres.
Exemple :

Code:

---

1 2 3

l1=[1,2,3,4,5,6,7,8,9,10] # ou l2 = [1,2,3,8,9,10,11,5,6,7]

---

trouver une fonction qui renvoie une liste de tuples constitués de n nombres qui se suivent à partir d'une liste de nombres. Cette liste et n étant fournis en paramètres de la fonction.
Exemple pour l1 avec n = 3 :
[(1,2,3),(4,5,6),(7,8,9)]
Exemple pour l2 avec n = 3 :
[(1,2,3),(8,9,10),(5,6,7)]
j'espère que c'est assez clair.
Ami calmant, J.P

Bonjour

Citation:

---

Envoyé par jurassic pork

j'espère que c'est assez clair.

---

avec les exemples oui ça va.

Code:

---

1 2 3 4 5

def genere(l, *, n=1): return tuple(l[i:i+n] for i in range(0, len(l) - len(l)%n, n))   l=tuple(range(1, 11)) print(genere(l, n=3))

---

Merci bien Sve@r cela semble fonctionner pour 3 ( j'ai remplacé ton tuple du return par un list car je voulais une liste) mais j'ai un problème par exemple avec n=2 avec cette liste :

Code:

---

l1=[1,2,3,4,18,19,20,21,22,100]

---

j'obtiens pour n=2 :

Citation:

---

[(1, 2), (3, 4), (18, 19), (20, 21), (22, 100)]

---

le dernier tuple n'est pas bon.

Citation:

---

Envoyé par jurassic pork

le dernier tuple n'est pas bon.

---

Pour obtenir une liste au lieu d'un tuple c'est un détail (moi je pars toujours du minimum nécessaire et ensuite, si besoin, on peut alors caster le retour de la fonction) mais je ne comprends pas pourquoi le dernier tuple n'est pas bon.
Ta liste initiale l1=[1,2,3,4,18,19,20,21,22,100] contient 10 éléments. Pour n=2 j'ai compris que ça devait retourner 5 tuples de 2 éléments⁽¹⁾ ce qui est bel et bien le cas. Qu'ai-je donc raté ???

(1) en fait là où j'ai eu une difficulté c'est quand la liste de départ n'était pas multiple de n. Dans mon premier essai ça renvoyait [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10,)] d'où cet empirique len(l) - len(l)%n pour arrêter à "multiple de n inférieur ou égal à len(l)"...

Citation:

---

Envoyé par Sve@r

Ta liste initiale l1=[1,2,3,4,18,19,20,21,22,100] contient 10 éléments. Pour n=2 j'ai compris que ça devait retourner 5 tuples de 2 éléments⁽¹⁾ ce qui est bel et bien le cas.

---

ben non en fait, 100 n'est pas 22+1 alors il ne faut prendre le tuple et en fait la fonction ne fonctionne pas (même pour 3 mes exemples sont mal choisis :oops: essayer avec [8,9,10,40,11,12,13,14,15,16] qui doit renvoyer [(8,9,10),(11,12,13),(14,15,16)] )

Salut,

Si on cherche un peu sur Internet pour voir ce qui existe déjà on tombe sur ce genre d'algorithmes...

- W

Citation:

---

Envoyé par jurassic pork

ben non en fait, 100 n'est pas 22+1 alors il ne faut prendre le tuple et en fait la fonction ne fonctionne pas (même pour 3 mes exemples sont mal choisis :oops: essayer avec [8,9,10,40,11,12,13,14,15,16] qui doit renvoyer [(8,9,10),(11,12,13),(14,15,16)] )

---

Ok. Le 40 fait un peu plus bien chier le monde quoi. Mais j'y suis arrivé.
Tout d'abord (diviser pour régner) une fonction qui part d'un point de la liste et qui, si elle trouve n éléments à suivre, renvoie ces n éléments sous forme de tuple. Sinon elle renvoie None.

Ensuite une boucle pour trouver, à chaque fois, le point de départ suivant selon la dernière valeur mémorisée. Et à partir de ce point elle regarde si elle peut récupérer n éléments suivants.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#!/usr/bin/env python3 # coding: utf-8   def genere(l, *, n=1): # Déjà la création du tuple def make(i): data=(l[i],) for j in l[i+1:i+n]: if j != data[-1] + 1: return None data=data + (j,) # for return data if len(data) == n else None # make()   # Traitement de la liste ret=list() i=0 while i < len(l): # Si élément en cours pas suivant dernier élément mémorisé # Ou si pas de génération # Alors on passe à l'élément suivant if (ret and l[i] != ret[-1][-1] + 1) or not (work:=make(i)): i+=1 continue # if   # On rajoute le tuple créé ret.append(work) i+=n # while return ret # genere()   l=[8, 9, 10, 40, 11, 12, 13, 14, 15, 16, 18, 19, 20] print(genere(l, n=3))

---

Hello,

Citation:

---

Envoyé par wiztricks

Salut,

Si on cherche un peu sur Internet pour voir ce qui existe déjà on tombe sur ce genre d'algorithmes...

- W

---

ben non j'ai cherché sur internet mais ce que je recherche exactement on ne le trouve pas ( suite de n éléments qui se suivent) et si tu as trouvé met nous le code :mouarf:

Ami calmant, J.P

Désolé Sve@r cela ne fonctionne toujours pas :
avec cette liste en entrée :

Code:

---

[1,2,3,4,18,19,20,21,22,100]]

---

pour n=3
j'obtiens [(1, 2, 3)] alors que j'attends [(1, 2, 3),(18,19,20)]
et pour n=2
j'obtiens [(1, 2), (3, 4)] alors que j'attends [(1, 2), (3, 4), (18,19), (20,21)]

EDIT: grillé

bonjour

Citation:

---

Envoyé par Sve@r

Mais j'y suis arrivé.

---

Oui, mais comme la demande n'est pas encore claire :aie:

Code:

---

1 2	l=[50, 51, 52, 8, 9, 10, 40, 11, 12, 13, 53, 54, 55, 14, 15, 16, 18, 19, 20] print(genere(l, n=3))

---

Ne retourne que les valeurs > 49 ... Les tuples doivent aussi se suivre ou que les nombres dans un tuple ???

Citation:

---

Envoyé par jurassic pork

Désolé Sve@r cela ne fonctionne toujours pas :
avec cette liste en entrée :

Code:

---

[1,2,3,4,18,19,20,21,22,100]]

---

pour n=3
j'obtiens [(1, 2, 3)] alors que j'attends [(1, 2, 3),(18,19,20)]
et pour n=2
j'obtiens [(1, 2), (3, 4)] alors que j'attends [(1, 2), (3, 4), (18,19), (20,21)]

---

Ok, c'était dans l'exemple précédent le "11" qui suivait le "10" (si on oblitère ce "40" parasite) qui m'a laissé croire qu'il fallait que la suite continue à la fin de la suite précédente.

Mais ça c'est facile à corriger. Suffit de supprimer le (ret and l[i] != ret[-1][-1] + 1) qui servait à gérer la continuation. Si pas besoin de continuation alors pas besoin de cette partie.
Le test devient alors simplement if not (work:=make(i)) qui checke juste la génération d'une suite. Et avec tes exemples ça donne bien le résultat demandé.

Citation:

---

Envoyé par papajoker

EDIT: grillé

---

Ah ben oui, 3h c'est une éternité dans ce forum 8-)

Citation:

---

Envoyé par papajoker

Les tuples doivent aussi se suivre ou que les nombres dans un tuple ???

---

Oui voilà, c'est bel et bien la question. Mais bon avec le nouveau test, ton exemple donne [(50, 51, 52), (8, 9, 10), (11, 12, 13), (53, 54, 55), (14, 15, 16), (18, 19, 20)] ce qui me semble (oui maintenant je joue la prudence :mrgreen:) correct...

Bravo Sve@r :applo: cela semble OK maintenant ! Entre temps j'avais demandé au démoniaque :evilred: ChatGPT qui m'a sorti une fonction (que j'ai du légèrement modifier) qui donne les mêmes résultats que la tienne :

Code:

---

1 2 3 4 5 6 7 8 9

def find_incremental_sequence(lst, n): lseq = [] i=0 while i < len(lst) - n + 1: if all(lst[i + j] == lst[i] + j for j in range(n)): lseq.append(tuple(lst[i:i + n])) i +=n-1 i +=1 return lseq

---

Code:

---

1 2 3 4 5

l = [1,2,3,8,9,10,11,5,6,7]   foo = lambda l,n: l and (l[:n]==[*range(l[0],l[0]+n)] and [(*l[:n],)] + foo(l[n:],n) or foo(l[1:],n))   print(foo(l,3))

---

Citation:

---

Envoyé par josmiley

foo = lambda l,n: l and (l[:n]==list(range(l[0],l[0]+n)) and [(*l[:n],)] + foo(l[n:],n) or foo(l[1:],n))

---

Impressionnant :hola:

Hello,
Effectivement c'est très impressionnant, c'est d'un niveau Gourou :applo: . Cela donne les mêmes résultats que les deux fonctions précédentes.

Ami calmant, J.P

Hello,

Ma proposition,

Code:

---

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

from itertools import pairwise   def find_incremental_sequences(lst, n): result = [] i = 0   while i <= len(lst) - n: subsequence = lst[i:i + n] if all(y - x == 1 for x, y in pairwise(subsequence)): result.append(tuple(subsequence)) i += n - 1 i += 1   return result   assert find_incremental_sequences([8,9,10,40,11,12,13,14,15,16], n=3) == [(8,9,10),(11,12,13),(14,15,16)] assert find_incremental_sequences([1,2,3,4,18,19,20,21,22,100], n=2) == [(1, 2), (3, 4), (18, 19), (20, 21)]

---

pairwise a été introduit dans le module itertools depuis la version python 3.10

Sve@r,

Citation:

---

Impressionnant

---

T'es sûr :D

1. Récursivité (souvent lent en python et limité)
2. Lisibilité
3. Copies nombreuses de listes (slice)

Sinon je peux comprendre que les oneliners sont toujours impressionnants mais passent très rarement les revues de code, surtout sur cette longueur de ligne.

Citation:

---

Envoyé par fred1599

Sinon je peux comprendre que les oneliners sont toujours impressionnants mais passent très rarement les revues de code, surtout sur cette longueur de ligne.

---

C'est clair , les perfs ne sont jamais au rdv avec ce genre d'exercice , mais je trouve cela tellement amusant :mrgreen:

Hello,
Désolé fred1599 et merci de t'être penché sur le problème mais je ne vous ai pas tout dit. La fonction doit être utilisée dans une macro python LibreOffice donc avec un python 3.8 et on ne peut pas employer pairwise. Une autre chose que je ne vous ai pas dite c'est que la liste en entrée est une liste de float car récupérer dans feuille du tableur calc c'est pour cela que dans la fonction de chatgpt j'ai rajouté un

Code:

---

lstint = list(map(int, lst))

---

je dois faire aussi cette conversion dans la fonction de josmiley. Par contre dans la fonction à Sve@r ça passe avec une liste de float en entrée.
J' ai fait un test de performance dans le cas réel avec 4000 lignes de 10 nombres pour trouver des suites de 3,4 et 5 nombres. Voici les résultats :
ChatGpt:

Citation:

---

0.1264035000003787
0.1163778000000093
0.10706149999987247

---

Sve@r:

Citation:

---

0.07142360000034387
0.0756098000001657
0.08020909999959258

---

josmiley:

Citation:

---

0.1208133000000089
0.11995089999982156
0.12660740000137594

---

La fonction de Sve@r est certainement plus rapide car il n'y a pas la conversion en entier à faire. Il y a peut-être moyen de s'en passer en adaptant le code dans les deux fonctions qui l'utilisent.

Ami calmant, J.P

Hello,

@jurassic_pork,

oui la version est importante, mais nous ne savions pas non plus que tu avais un besoin d'efficacité (4000 lignes).

Autre essai,

Code:

---

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

def find_incremental_sequences(lst, n): results = [] i = 0   while i <= len(lst) - n: is_incremental = True for j in range(n - 1): if lst[i + j + 1] - lst[i + j] != 1: is_incremental = False break   if is_incremental: results.append(tuple(lst[i:i + n])) i += n else: i += 1   return results   assert find_incremental_sequences([8,9,10,40,11,12,13,14,15,16], n=3) == [(8,9,10),(11,12,13),(14,15,16)] assert find_incremental_sequences([1,2,3,4,18,19,20,21,22,100], n=2) == [(1, 2), (3, 4), (18, 19), (20, 21)]

---

fred ton essai semble pas mal voilà ce que j'obtiens en performance :

Citation:

---

0.06364769999709097
0.061388799997075694
0.05734239999947022

---

Mieux que la fonction de Sve@r


et à noter que finalement la fonction de chatGpt n'a pas besoin de la conversion en entier en on obtient alors comme performance :

Citation:

---

0.10574530000303639
0.10048109999843291
0.09056110000165063

---

mais tout ceci n'est qu'anecdotique car la différence de performance entre des temps de l'ordre de 100ms et de 60ms ne se verra pas car le temps total du traitement dans LibreOffice sera surtout celui du transfert des données entre la feuille de calcul et le python.

Merci à tous pour votre participation

Citation:

---

transfert des données entre la feuille de calcul et le python.

---

Quelle est ta méthode pour faire cela ?

voici le code pour prendre les données sur la feuille , faire le traitement pour une suite de n éléments et afficher les résultats sur la feuille :

Code:

---

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

def calculSuite(n): #ODOC.NamedRanges.getByName("ListeResultats").getReferredCells().clearContents(31) plage = ODOC.NamedRanges.getByName("ListeNombres").getReferredCells() # on récupere la liste des nombres en une seule fois valeurs = plage.getDataArray() maListe = [] for valeur in valeurs: maListe += find_incremental_sequence(list(valeur), n) result = count_and_order_tuples(maListe) listres=[] for tpl, count in result: listres.append([str(tpl),count]) sheet = ODOC.CurrentController.ActiveSheet cursor = sheet.createCursorByRange(sheet.getCellByPosition(10 + (n-3)*2,1)) cursor.collapseToSize( len(listres[0]) , len(listres) ) cursor.setDataArray(listres)

---

Pièce jointe 650340

Dans le traitement en plus de la fonction dont il est question dans cette discussion, on met tous les tuples dans une liste et on classe par nombre de fois qu'un tuple est présent( count_and_order_tuples) et on va mettre dans 2 colonnes de la feuille, les tuples sous forme de chaine et dans la colonne à côté le nombre de fois qu'il est présent.
En fait les fonctions getDataArray() et setDataArray() ne sont pas si lentes que cela car pour 4000 lignes de 10 nombres le temps d'exécution est de 60 ms par appel. C'est plutôt le temps d'affichage dans la feuille qui prend du temps ( quelques secondes).

Mieux la liste comprehension

Code:

---

maListe = [find_incremental_sequence(list(valeur), n) for valeur in valeurs]

---

et

Code:

---

listres = [[str(tpl), count] for tpl, count in result]

---

Citation:

---

C'est plutôt le temps d'affichage dans la feuille qui prend du temps ( quelques secondes).

---

Pour cela on pourrait limiter le nombre d'opérations d'écriture si possible. Plutôt que ligne par ligne, tu gardes en mémoire les données à écrire et tu écris le tout en une seule opération.

Citation:

---

Envoyé par fred1599

Pour cela on pourrait limiter le nombre d'opérations d'écriture si possible. Plutôt que ligne par ligne, tu gardes en mémoire les données à écrire et tu écris le tout en une seule opération.

---

des écritures il n'y en pas beaucoup un setDataArray pour une série de n nombres donc 3 au total pour 3 séries et finalement si on regarde le gif animé on voit que le traitement total pour 3 types de série est rapide quand même

plus classique du coup, aucune idée des perfs:

Code:

---

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

def foo(l,n): n -= 1 ln = len(l)-n e = 1 idx = 0 out = []   while e<ln: if l[e-1]==l[e]-1: idx += 1 if idx == n: out.append((*l[e-n:e+1],)) idx = 0 e+=1 else: idx = 0 e+=1 return out

---

Hello,

Citation:

---

Envoyé par josmiley

plus classique du coup, aucune idée des perfs:

---

ben cela m'a l'air d'être la plus performante, voici ce que j'obtiens comme temps :

Citation:

---

0.03163999999992484
0.02775870000004943
0.022576200000003155

---

Ami calmant, J.P

Citation:

---

Envoyé par fred1599

Sinon je peux comprendre que les oneliners sont toujours impressionnants

---

Oui c'est ça. J'ai bien vu certains soucis (surtout la récursivité) mais c'est le onliner qui est magnifique 8-)

Citation:

---

Envoyé par jurassic pork

La fonction de Sve@r est certainement plus rapide car il n'y a pas la conversion en entier à faire.

---

Oui enfin j'ai pas non plus inventé l'eau tiède. Je me suis contenté d'écrire l'algorithme "glouton" correspondant (en fait j'ai vu le besoin initial comme rechercher les sous-chaines d'une chaine). :mrgreen:

Citation:

---

Envoyé par jurassic pork

fred ton essai semble pas mal voilà ce que j'obtiens en performance :

Mieux que la fonction de Sve@r

---

:pleure::pleure::triste:

Hello,

Citation:

---

Oui c'est ça. J'ai bien vu certains soucis (surtout la récursivité) mais c'est le onliner qui est magnifique

---

C'est vrai qu'il faut se triturer l'esprit surtout en pensant récursivité à créer ce genre de oneliner (pas onliner ;) ).

J'ai beaucoup de difficulté à créer ce genre de ligne, je manque de pratiques... il faut pour cela que je trouve le oneliner assez intuitif, sinon je ne cherche pas à le créer naturellement.

Concernant l'efficacité, il y a mieux, voir le dernier code de @josmiley :D

Citation:

---

Envoyé par fred1599

J'ai beaucoup de difficulté à créer ce genre de ligne, je manque de pratiques... il faut pour cela que je trouve le oneliner assez intuitif, sinon je ne cherche pas à le créer naturellement.

---

une bonne façon de s'initier pour moi c'est tenter l 'apprentissage d' haskell, sans aller jusqu'au bout ça m'a permis une approche différente de la prog.

Oui pour la partie récursivité haskell a un intérêt, mais pour les oneliners complexes, pas sûr que s'appuyer sur un langage fonctionnel ai un intérêt.