Comment vérifier qu'une séquence est strictement monotone ou qu'il y a un tournant où les deux côtés sont strictement monotones?

J'utilise une combinaison de np.sgn et np.diff pour vérifier les parties ascendantes / descendantes de la séquence. D'après vos exemples en l2 et l4, les éléments doubles (où diff == 0) ne comptent pas comme croissant ou décroissant. Ceux-ci sont rejetés dans la première clause if-else . Dans la plupart des cas, le np.sign(np.diff(x)) est tous les -1 et 1, selon les parties ascendantes / descendantes. Nous calculons un deuxième np.diff pour voir combien de points de retournement il y a et retournons Vrai / Faux en conséquence.

Voir le code ci-joint :)

1 True
2 False
3 True
4 False
5 True
6 True
7 False
8 False
9 False
10 False
11 False

Cela produit:

import numpy as np
  
def legal_seq(seq):
    arr = np.array(seq)
    diffs = np.diff(arr) 
    sgn_diff = np.sign(diffs)
    if np.isin(0, sgn_diff): # if the difference is 0, we reject the seq
        return False
    else:
        sgn_diff2 = np.diff(sgn_diff) # the sgn_diff is only 1's and -1's we need to count how many constant segments there are, so we use np.diff again
        num_turning_points = len(np.where(sgn_diff2)[0]) # np.where will see how many non-zero elements there are. nonzero elements in the np.diff are turning points, so we count these
        if num_turning_points < 2: # if num_turning_points is 0, the seq is mono. if num_turning_points is 1, we return True. Otherwise, False is returned.
            return True
        else:
            return False

## TESTING ##
l1=[1,3,5,6,7]
l2=[1,2,2,3,4]
l3=[5,4,3,2,1]
l4=[5,5,3,2,1]
l5=[1,2,3,4.1,3,2]
l6=[3,2,1,0.4,1,2,3]
l7=[1,2,10,4,8,9,2]
l8=[1,2,3,4,4,3,2,1]
l9=[-0.05701686,  0.57707936, -0.34602634, -0.02599778]
l10=[ 0.13556905,  0.45859   , -0.34602634, -0.09178798,  0.03044908]
l11=[-0.38643975, -0.09178798,  0.57707936, -0.05701686,  0.00649252]

ls = [l1, l2, l3, l4, l5, l6, l7, l8, l9, l10, l11]
for i,l in enumerate(ls):
    print(i + 1, count_turning_points(l))

IIUC, vous avez 3 cas:

• Seule une séquence monotone strictement croissante qui couvre toute la séquence
• Seule une séquence monotone strictement décroissante qui couvre toute la séquence
• Une séquence monotone à la fois strictement croissante et décroissante, dont la somme couvre toute la séquence

Vous pouvez donc faire ce qui suit:

[1, 3, 5, 6, 7] True
[1, 2, 2, 3, 4] False
[5, 4, 3, 2, 1] True
[5, 5, 3, 2, 1] False
[1, 2, 3, 4.1, 3, 2] True
[3, 2, 1, 0.5, 1, 2] True
[3, 2, 1, 0.4, 1, 2, 3] True
[1, 2, 10, 4, 8, 9, 2] False
[1, 2, 3, 4, 4, 3, 2, 1] False
[-0.05701686, 0.57707936, -0.34602634, -0.02599778] False
[0.13556905, 0.45859, -0.34602634, -0.09178798, 0.03044908] False
[-0.38643975, -0.09178798, 0.57707936, -0.05701686, 0.00649252] False

Production

from scipy.signal import argrelmin, argrelmax
import pandas as pd


def is_strictly_monotonic_increasing(s):
    return s.is_unique and s.is_monotonic_increasing


def is_strictly_monotonic_decreasing(s):
    return s.is_unique and s.is_monotonic_decreasing


def find_targeted_seq(lst):
    ser = pd.Series(lst)

    if is_strictly_monotonic_increasing(ser) or is_strictly_monotonic_decreasing(ser):
        return True

    minima, *_ = argrelmin(ser.values)
    if len(minima) == 1:  # only on minimum turning point
        idx = minima[0]
        return is_strictly_monotonic_decreasing(ser[:idx]) and is_strictly_monotonic_increasing(ser[idx:])

    maxima, *_ = argrelmax(ser.values)
    if len(maxima) == 1:  # only on maximum turning point
        idx = maxima[0]
        return is_strictly_monotonic_increasing(ser[:idx]) and is_strictly_monotonic_decreasing(ser[idx:])

    return False


data = [[1, 3, 5, 6, 7],  # l1
        [1, 2, 2, 3, 4],  # l2
        [5, 4, 3, 2, 1],  # l3
        [5, 5, 3, 2, 1],  # l4
        [1, 2, 3, 4.1, 3, 2],  # l5
        [3, 2, 1, 0.5, 1, 2],  # this value was added in addition to the existing ones
        [3, 2, 1, 0.4, 1, 2, 3],  # l6
        [1, 2, 10, 4, 8, 9, 2],  # l7
        [1, 2, 3, 4, 4, 3, 2, 1],  # l8
        [-0.05701686, 0.57707936, -0.34602634, -0.02599778],  # l9
        [0.13556905, 0.45859, -0.34602634, -0.09178798, 0.03044908],  # l10
        [-0.38643975, -0.09178798, 0.57707936, -0.05701686, 0.00649252]]  # l11

for datum in data:
    print(datum, find_targeted_seq(datum))

Ni la bibliothèque standard de Python ni NumPy n'ont de primitive spécifique pour résoudre cette tâche. Cependant, la méthode traditionnelle dans NumPy est d'examiner les différences en utilisant np.diff() .

Pour étudier les points de retournement, vous pouvez utiliser respectivement np.argmin() et np.argmax() .

La condition de monotonicité stricte correspond à: np.all(np.diff(arr) > 0) (croissant) ou np.all(np.diff(arr) < 0) (décroissant). L'exigence d'un point de retournement (pivot) équivaut à trouver ce point de retournement et à vérifier que la séquence est séparément monotone. Pour plusieurs minima ou maxima consécutifs, si l'on utilise les premiers minima ou maxima rencontrés et vérifie la monotonie de la branche gauche excluant ces minima ou maxima, cela suffit à garantir que deux minima ou maxima consécutifs seront correctement identifiés.

Par conséquent, une implémentation simple suit:

for func in funcs:
    print(func.__name__)
    %timeit [func(seq) == result for seq, result in data]
    print()

# find_targeted_seq_np
# 1000 loops, best of 3: 530 µs per loop

# find_targeted_seq_np2
# 10000 loops, best of 3: 187 µs per loop

# find_targeted_seq_pd
# 100 loops, best of 3: 4.68 ms per loop

# find_targeted_seq
# 100000 loops, best of 3: 14.6 µs per loop

# find_targeted_seq_nb
# 10000 loops, best of 3: 19.9 µs per loop

(C'est fondamentalement la même idée que dans la réponse de @ DaniMesejo ).

Une autre option serait d'utiliser une combinaison de np.diff() , np.sign() et np.count_nonzero() pour compter le nombre de fois où il y a un changement de monotonie. Si c'est 0 ou 1, alors la séquence est valide. Éviter les éléments répétitifs est intégré dans le comptage des changements de signe, sauf lorsque les éléments répétitifs sont au début ou à la fin de la séquence et cette situation doit être vérifiée explicitement. Cela conduit à une solution très concise:

data = (
    ((1, 3, 5, 6, 7), True),  # l1
    ((1, 2, 2, 3, 4), False),  # l2
    ((5, 4, 3, 2, 1), True),  # l3
    ((5, 5, 3, 2, 1), False),  # l4
    ((1, 2, 3, 4.1, 3, 2), True),  # l5
    ((3, 2, 1, 0.5, 1, 2), True),  # this value was added in addition to the existing ones
    ((3, 2, 1, 0.4, 1, 2, 3), True),  # l6
    ((1, 2, 10, 4, 8, 9, 2), False),  # l7
    ((1, 2, 3, 4, 4, 3, 2, 1), False),  # l8
    ((-0.05701686, 0.57707936, -0.34602634, -0.02599778), False),  # l9
    ((0.13556905, 0.45859, -0.34602634, -0.09178798, 0.03044908), False),  # l10
    ((-0.38643975, -0.09178798, 0.57707936, -0.05701686, 0.00649252), False),  # l11
)


funcs = find_targeted_seq_np, find_targeted_seq_np2, find_targeted_seq_pd, find_targeted_seq, find_targeted_seq_nb

for func in funcs:
    print(func.__name__, all(func(seq) == result for seq, result in data))
# find_targeted_seq_np True
# find_targeted_seq_np2 True
# find_targeted_seq_pd True
# find_targeted_seq True
# find_targeted_seq_nb True

(C'est fondamentalement la même idée que dans la réponse de @ yonatansc97 , mais sans utiliser np.isin() comme suggéré dans les commentaires de @DaniMesejo).

Alternativement, on peut envisager d'utiliser la boucle explicite. Cela a l'avantage d'être considérablement plus efficace en mémoire et de bien meilleures propriétés de court-circuit:

from scipy.signal import argrelmin, argrelmax
import pandas as pd


def is_strictly_monotonic_increasing(s):
    return s.is_unique and s.is_monotonic_increasing


def is_strictly_monotonic_decreasing(s):
    return s.is_unique and s.is_monotonic_decreasing


def find_targeted_seq_pd(lst):
    ser = pd.Series(lst)
    if is_strictly_monotonic_increasing(ser) or is_strictly_monotonic_decreasing(ser):
        return True
    minima, *_ = argrelmin(ser.values)
    if len(minima) == 1:  # only on minimum turning point
        idx = minima[0]
        return is_strictly_monotonic_decreasing(ser[:idx]) and is_strictly_monotonic_increasing(ser[idx:])
    maxima, *_ = argrelmax(ser.values)
    if len(maxima) == 1:  # only on maximum turning point
        idx = maxima[0]
        return is_strictly_monotonic_increasing(ser[:idx]) and is_strictly_monotonic_decreasing(ser[idx:])
    return False

De plus, si la stabilité de type des éléments de la séquence peut être garantie, elle peut être facilement accélérée via Numba:

import numba as nb


_find_targeted_seq_nb = nb.njit(find_targeted_seq)


def find_targeted_seq_nb(seq):
    return _find_targeted_seq_nb(np.array(seq))

À titre de comparaison, ici, il est rapporté une implémentation utilisant pandas (qui fournit quelques primitives pour le contrôle de monotonie) et scipy.signal.argrelmin() / scipy.signal.argrelmax() pour trouver des points de retournement (ce code est sensiblement le même que celui trouvé dans @ Réponse de DaniMesejo ), par exemple:

def find_targeted_seq(seq):
    n = len(seq)
    changes = 0
    x = seq[1]
    last_x = seq[0]
    diff = x - last_x
    if diff > 0:
        monotonic = 1
    elif diff < 0:
        monotonic = -1
    else:  # diff == 0
        return False
    for i in range(1, n):
        x = seq[i]
        diff = x - last_x
        if diff == 0:
            return False
        elif (diff > 0 and monotonic == -1) or (diff < 0 and monotonic == 1):
            changes += 1
            monotonic = -monotonic
        if changes > 1:
            return False
        last_x = x
    return True

Ces solutions appliquées à l'entrée donnée donnent toutes les bons résultats:

import numpy as np


def find_targeted_seq_np2(seq):
    diffs = np.diff(seq)
    return \
        diffs[0] != 0 and diffs[-1] != 0  \
        and np.count_nonzero(np.diff(np.sign(diffs))) < 2

Dans le temps, quelques benchmarks simples sur les données proposées indiquent clairement que le bouclage direct (avec ou sans accélération Numba) est le plus rapide. La deuxième approche Numpy devient beaucoup plus rapide que la première approche NumPy, tandis que l'approche basée sur les pandas est la plus lente:

import numpy as np


def find_targeted_seq_np(seq):
    diffs = np.diff(seq)
    incr = diffs > 0
    decr = diffs < 0
    if np.all(incr) or np.all(decr):
        return True
    maximum = np.argmax(seq)
    if np.all(incr[:maximum]) and np.all(decr[maximum:]):
        return True
    minimum = np.argmin(seq)
    if np.all(decr[:minimum]) and np.all(incr[minimum:]):
        return True
    return False

Alors que la boucle directe est plus rapide pour ces données de test que les approches basées sur NumPy sur l'entrée donnée, ces dernières devraient mieux évoluer avec une taille d'entrée plus grande. L'approche Numba est susceptible d'être plus rapide que les approches NumPy à toutes les échelles.