Compter les longueurs de sous-liste viables d'un tableau

Question

Il s'agit d'une fonction de fitness d'un algorithme génétique, il est donc important que je puisse le faire aussi efficacement que possible, car il sera répété encore et encore.

Disons qu'il existe une fonction foo(int[] tableau) qui renvoie vrai si le tableau est un "bon" tableau et faux si le tableau est un "mauvais" tableau. Ce qui le rend bon ou mauvais n'a pas d'importance ici. Ce n'est pas la fonction que nous définissons ici. Elle est simplement utilisée par la fonction que j'essaie de comprendre.

Étant donné le tableau complet [1,6,8,9,5,11,45,16,9], disons que le sous tableau [1,6,8] est un "bon" tableau tel que défini par foo() et que [9,5,11,45] est un "bon" tableau tel que défini par foo(). De plus, [5,11,45,16,9] est un "bon" tableau, et aussi le plus long "bon" sous tableau. Remarquez que si [9,5,11,45] est un "bon" tableau, et [5,11,45,16,9] un "bon" tableau, [9,5,11,45,16,9] est un "mauvais" tableau.

Remarquez que ce n'est pas la fonction foo() que nous définissons. Tout ce qui nous intéresse, c'est de prendre tous les sous-réseaux possibles du tableau complet, de les envoyer à foo(), de déterminer s'ils sont bons ou mauvais, et de compter leurs longueurs. Le seul problème est que nous ne voulons pas compter les "bons" sous-groupes de "bons" sous-groupes, mais il y a des "bons" sous-groupes qui peuvent commencer dans un autre bon sous-groupe, mais se terminer en dehors de celui-ci.

Nous voulons le nombre de longueurs de tous les "bons" tableaux, mais pas des sous-réseaux de "bons" tableaux. De plus, comme décrit ci-dessus, un "bon" tableau peut commencer au milieu d'un autre "bon" tableau, mais la combinaison des deux peut être un "mauvais" tableau.

Answer 1

Vous avez besoin d'un algorithme récursif qui enregistre ses résultats dans une structure de données externe.

Il devrait prendre les index de début et de fin de sous-matrice comme paramètres, vérifiez si c'est bon ou pas.

Si le tableau est bon, alors son start y end Les index doivent être stockés dans cette structure externe. Sinon, vous devez faire 2 appels récursifs : de start indice pour end-1 et de l'indice start+1 indice pour end l'index.

public void getLargestGoodArrays (int start, int end) {
   if (isGood (start, end) {
      saveGoodArray (start, end);
   } else {
      //here you should iterate through all already found good arrays to check whether the array with larger bounds already saved
      if (!isSubarrayOfGoodArray (start, end - 1)) {
         getLargestGoodArrays (start, end - 1);
      }
      if (!isSubarrayOfGoodArray (start + 1, end)) {
         getLargestGoodArrays (start + 1, end);
      }          
   }
}