Recherche les plus longues tranches d'un tableau contenant des valeurs séparées

Question

J'ai un très long tableau unidimensionnel d'entiers positifs. À partir d'une extrémité, j'ai besoin de trouver les plus longues tranches/morceaux du tableau qui ont des valeurs qui sont à au moins un nombre de tous les constituants de cette tranche.

C'est-à-dire que je souhaite effectuer un partitionnement du tableau (en partant de la gauche) de sorte que chaque partition contienne des éléments éloignés de tous les autres éléments de cette partition.

Par exemple:

1. [1,1,9,5,3,8,7,4,1,2] -> [1], [1,9,5,3], [ 8], [7,4,1], [2]
2. [1,5,9,1,3,6,4,2,7,0] -> [1,5,9], [1 , 3,6,4], [2,7,0]

Ci-dessous, j'ai écrit un petit code en Fortran qui me permettra de trouver le premier point de récurrence d'une valeur précédente.

• masque est un tableau LOGIQUE
tableau
• est le tableau en question
• n est la longueur du tableau

Je peux facilement étendre ce pour trouver la partition complète. Donc, ma question est, y a-t-il une meilleure façon (alorithme) de faire cela? Quand je dis mieux, je veux dire la vitesse. Cela ne me dérange pas un coût de mémoire.

Answer 1

Conceptuellement il pourrait ressembler à quelque chose comme ça ...

DO i = 1,n-1 
    Delta(I) = array(I+1) - array(I) 
ENDDO 

iMask = 0 
WHERE(ABS(Delta) < 2) iMask =1 
ALLOCATE(splits(SUM(iMask))) 

K=0 
DO I = 1, n-1 
    IF(iMask(I) == 0) CYCLE 
    K = K +1 
    Splits(K) = I 
ENDDO 

!... DEALLOCATE(Splits) 

Ensuite, il suffit d'imprimer les données entre les valeurs des scissions, qui pourrait être hors d'un compte, et vous devrez peut-être faire quelque chose pour la Nième point, donc cela dépend un peu de votre implémentation et si votre delta est "trop ​​le point suivant" ou "du dernier point".

Dans ce cas, j'ai utilisé imask comme un entier plutôt que logique afin que je puisse utiliser SUM.

Answer 2

Ma première réaction est l'approche naïve:

• sauver des bornes d'index sur la partition que vous êtes actuellement en expansion (partitionNumberiStart-iEnd)
• Prenez le point suivant avec un indice iEnd+1 et boucle de iStartiEnd testant que le point candidat n'est pas dans 1 des membres actuels
• Si le candidat échoue au test d'inclusion, démarrez-le dans sa propre partition en réinitialisant iStart et i ncrementing partitionNumber
• Incrément iEnd.

Si vous attendez que les partitions soient généralement assez courtes, cela devrait être assez rapide.Si vous attendez de longues chaînes d'entiers croissants ou décroissants, vous pouvez enregistrer les min et max de valeurs dans la partition, y compris un test rapide pour voir si votre candidat est en dehors de la plage.

Je n'ai pas testé cela et mon fortran pourrait être un peu rouillé, mais je pense qu'il représente l'algorithme ci-dessus.

partitionNumber = 1 
iStart = 1 
iEnd = 1 
iCandidate = iEnd + 1 
arrayMember(iStart) = partitionNumber 
DO WHILE (iCandidate <= N) 
    DO j = iStart,iEnd 
     IF (ABS(array(iCandidate)-array(j)) < 2) 
      partitionNumber = partitionNumber + 1 
      iStart = iCandidate 
      EXIT 
     END IF 
    END DO 
    arrayMember(iCandidate) = partitionNumber 
    iEnd = iEnd + 1 
    iCandidate = iEnd + 1 
END DO 

Fonctionnant sur vos deux exemples, je l'espère pour revenir arrayMember avec des entrées

1. [1,1,9,5,3,8,7,4,1,2] -> [1,2,2,2,2,3,4,4,4,5] (REPRÉSENTE [1],[1,9,5,3],[8],[7,4,1],[2])
2. [1,5,9,1,3,6,4,2,7,0] -> [1,1,1,2,2,2,3,3,3,3] (représente [1,5,9],[1,3,6],[4,2,7,0])

Je suis pas tout à fait sûr je comprends comment vous étendez votre version à toutes les partitions, mais cette mi ght sauvegarder sur la définition mask de taille MAX(array)?