Comment toutes les séquences de sortie la plus longue baisse

Question

Supposons que j'ai un tableau d'entiers ayant une longueur $ N $. Comment peut-sortie I toutes les plus longues séquences décroissante? (A-séquence est constituée d'éléments de la matrice qui ne sont pas à être consecustive, par exemple $ (3,2,1) $ est une sous-séquence décroissante de $ (7,3,5,2,0,1).) Je sais comment calculer la longueur des plus longues séquences décroissantes, mais ne savent pas comment signaler toutes les plus longues séquences décroissantes.

pseudocode sera utile.

Answer 1

Considérons la séquence suivante en tant que votre entrée:

$$ n, n-2, n-1, n-3, n-5, n-4, n-6, n-8, n-7, n-9, ...., n- 3 \ cdot k - 2, n-3 \ cdot k - 1, n-3 \ cdot k - 3, .... $$

pour la simplicité suppose $ n = 3 \ cdot t + 1 $, la plus longue longueur de suite décroissante sera $ t $ et le nombre de longueur de suite décroissante $ t $ est 2 $ ^ t $.

nombre de solutions est avilable $ \ theta (2 ^ {n / 3}) $. Mais pourquoi il est si, modèle simplement avec DAG, prendre soin il y a un avantage de $ a $ ? $ b $, si $ a> b $ et $ b $ est après $ a $ en séquence originale.

parce que la taille de sortie peut être exponentielle, votre meilleur choix est de créer DAG, et de trouver tous les chemins les plus longs DAG ou de toute autre manière qui énumère toutes les façons acceptables.

Answer 2

-a fonction auxiliaire récursif

    list form_longest_sublist_from(list array,list buffer,from) 
            add array[from] to buffer

            list ret as copy of buffer
            from i = from - 1 to -1 step -1
                   if last buffer > array[i] 
                   list sbuffer
                   sbuffer = form_longest_sublist_from(array,buffer,i);
                   if length sbuffer > length ret
                      ret = sbuffer;
                   endif
                endif
            endfor
            return ret;
    endfunc

• L'algorithme pour utiliser la fonction

  list of lists arrayoflongestlist
      list buffer;
      from i = length array - 1 to -1 step -1
          clear buffer
          add array[i] to buffer
          from x = i - 1 to -1 step -1
              if(array[x] < last buffer
                  list sbuffer;
                  sbuffer = form_longest_sublist_from(array,buffer,x);
                  if length sbuffer > length buffer)
                      buffer = sbuffer;
                              endif
              endif
          endfor
              if length arrayoflongestlist > 0
                     if length (last arrayoflongestlist) < length buffer
                              clear arrayoflongestlist
                              add buffer to arrayoflongestlist
                     endif
                     else if length (last arrayoflongestlist) == length buffer
                  add buffer to arrayoflongestlist
              endif
  
                     if length (last arrayoflongestlist) > i)
                  break;
          else
              add buffer to arrayoflongestlist
          endif
      endfor
  

Je refit essentiellement l'algorithme entier pour être un ajustement pour le problème.

L'idée de base est de commencer à partir de chaque point possible (chaque élément) dans la matrice et à former tous les sous-listes décroissantes possibles en allant disposition par le reste de la matrice et de voir quels éléments sont plus petits et en utilisant ces éléments pour démarrer une récursion qui fait le même mentionné précédemment à partir de ce point et en filtrant ensuite les récursions pour la plus longue liste donnée en arrière.

Mon pire / BestCase scénarios possibles mentionné plus haut sont la cause pas correct compte tenu de cet algorithme.

Answer 3

Pour toute suite décroissante, mémoriser les positions de départ dans un autre tableau.

for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

Maintenant, la température de tableau contiendra des positions initiales et finales de toutes les séquences baisse consécutive. Puis les imprimer