Contexte

Un arbre binaire est un arbre enraciné dont chaque nœud a au plus deux enfants.

Un arbre binaire étiqueté est un arbre binaire dont chaque nœud est étiqueté avec un entier positif; de plus, toutes les étiquettes sont distinctes .

Un BST (arbre de recherche binaire) est un arbre binaire étiqueté dans lequel l'étiquette de chaque nœud est supérieure aux étiquettes de tous les nœuds de son sous-arbre gauche et plus petite que les étiquettes de tous les nœuds de son sous-arbre droit. Par exemple, ce qui suit est un BST:

La traversée en précommande d'un arbre binaire étiqueté est définie par le pseudo-code suivant.

function preorder(node)
    if node is null then
        return
    else
        print(node.label)
        preorder(node.left)
        preorder(node.right)

Voir l'image suivante pour obtenir une meilleure intuition:

Les sommets de cet arbre binaire sont imprimés dans l'ordre suivant:

F, B, A, D, C, E, G, I, H

Vous pouvez en savoir plus sur les BST ici et en savoir plus sur le parcours de précommande ici .

Défi

Étant donné une liste d'entiers $a$ , votre tâche consiste à déterminer s'il existe un BST dont la traversée en précommande imprime exactement $a$ .

Contribution

• Une liste non vide d'entiers positifs distincts $a$ .
• Facultativement, la longueur d' $a$ .

Production

• Une valeur vraie si $a$ est la traversée de précommande de certains BST.
• Une valeur de falsey sinon.

Règles

• Règles standard pour les soumissions valides , les E / S , les failles s'appliquent.
• C'est le code-golf , donc la solution la plus courte (en octets) l'emporte. Comme d'habitude, ne laissez pas les solutions ridiculement courtes dans les langues de golf vous décourager de poster une réponse plus longue dans la langue de votre choix.
• Ce n'est pas une règle, mais votre réponse sera mieux reçue si elle comprend un lien pour tester la solution et une explication de son fonctionnement.

Exemples

Input                   ---->   Output

[1]                     ---->   True
[1,2,3,4]               ---->   True
[5,1,4,2,3]             ---->   True
[5,4,3,2,1,6,7,8,9]     ---->   True
[4,2,1,3,6,5,7]         ---->   True
[8,3,1,6,4,7,10,14,13]  ---->   True
[2,3,1]                 ---->   False
[6,3,2,4,5,1,8,7,9]     ---->   False
[1,2,3,4,5,7,8,6]       ---->   False
[3,1,4,2]               ---->   False

Consultez ce lien (gracieuseté de Kevin Cruijssen ) pour avoir un aperçu visuel des exemples.

JavaScript (Node.js) , 49 octets

a=>!a.some((p,i)=>a.some((q,j)=>q>p&a[j+=j>i]<p))

Essayez-le en ligne!

En utilisant le fait que pour le tableau $a_0 ... a_{n-1}$ , $a$ est le pré-commande traversal de certains BST ssi $\forall 0\le i<j<n; a_i<a_{j-1} \implies a_i<a_j$ tient.

Grâce à Arnauld , économisez 1 octet.

Gelée , 7 octets

ŒPŒ¿€4ḟ

Essayez-le en ligne!

Renvoie [4]pour les traversées, sinon[] .

Utilise essentiellement l'algorithme de tsh: la condition "disqualifiante" pour une traversée de précommande est une sous- séquence de 3 éléments qui ressemble à [moyen, haut, bas] . (Par exemple, [20, 30, 10].)

Nous vérifions de manière équivalente toutes les sous-séquences de n'importe quelle longueur qui ont l'index 4 dans leurs listes de permutation, qui sont toutes des listes triées comme [a ₁ … a _k cdb] où les a _i sont triées et a _i <b <c <d . (Chacune de ces listes est disqualifiante si nous regardons les trois derniers éléments, et chaque liste disqualifiante est évidemment de cette forme.)

ŒP          All subsequences.
  Œ¿€       Permutation index of each.
     4ḟ     Set difference of {4} and this list.

Preuve

Un parcours de précommande ne contient aucune sous-séquence disqualifiante

Cas de base: traversée (•) est la liste vide. ✓

Induction: traversal (t) est: t.root ++ traversal (t.left) ++ traversal (t.right) .

Soit [a, b, c] une sous-séquence de celui-ci. Nous montrerons que c <a <b est impossible.

• Si t.root = a , alors c <a <b nécessite c ∈ t.left et b ∈ t.right , donc [a, b, c] est le mauvais ordre.
• Si a, b, c ∈ t. Gauche ou a, b, c ∈ t. Droit . , utilisez l'hypothèse d'induction.
• Si a ∈ t. Gauche et c ∈ t. Droite alors c> a .

Une liste d'entiers distincts sans sous-séquences disqualifiantes est le parcours de précommande d'un BST

Si la liste est vide, c'est la traversée du BST trivial •.

Si la liste est head suivie de tail :

• Soit moins le préfixe le plus long de la queue des éléments moins que la tête , et que plus soit le reste de la liste.
• Alors plus [1]> tête , et tous les autres [i] sont plus grands que tête aussi (sinon [tête, plus [1], plus [i]] serait une sous-séquence disqualifiante).
• Recurse: tourner moins et plus en BSTS.

• Maintenant, notre liste est la traversée de

                   head
                  /    \
           BST(less)   BST(more),
  

  et cet arbre est un BST valide.

Java 10, 94 octets

a->{var r=0>1;for(int j=a.length-1,i;j-->0;)for(i=0;i<j;)r|=a[j]>a[i]&a[j+1]<a[i++];return!r;}

Réponse JavaScript du port de @tsh .

Essayez-le en ligne.

Explication:

a->{                      // Method with integer-array parameter and boolean return-type
  var r=0>1;              //  Result-boolean, starting at false
  for(int j=a.length-1,i;j-->0;)
                          //  Loop `j` in the range (length-1, 0]:
    for(i=0;i<j;)         //   Inner loop `i` in the range [0, j):
      r|=                 //    If any are true, change the result to true as well:
         a[j]>a[i]        //     The `j`'th item is larger than the `i`'th item
         &a[j+1]<a[i++];  //     And the `j+1`'th item is smaller than the `i`'th item
  return!r;}              //  After the nested loop, check if the boolean is still false

Rubis , 46 40 38 octets

f=->r{a,*b=r;!a||b==b&[*0..a]|b&&f[b]}

Essayez-le en ligne!

Cela fonctionne en prenant récursivement le premier élément acomme pivot et en vérifiant si le reste du tableau peut être divisé en deux (en utilisant l'intersection et l'union: supprimez d'abord tous les éléments> a, puis ajoutez-les à nouveau à droite et vérifiez si quelque chose a modifié).

Retina 0.8.2 , 31 octets

\d+
$*
M`\b((1+)1+,).*\1\2\b
^0

Essayez-le en ligne! Le lien inclut des cas de test. Utilise l'algorithme de @ tsh. Explication:

\d+
$*

Convertissez en unaire.

M`\b((1+)1+,).*\1\2\b

Trouvez les nombres qui se trouvent entre deux nombres décroissants consécutifs consécutifs.

^0

Vérifiez que le nombre de correspondances est nul.

Perl 6 , 38 octets

!*.combinations(3).grep:{[>] .[1,0,2]}

Essayez-le en ligne!

Explication

 *.combinations(3)  # All combinations of 3 elements a,b,c
!                 .grep:{            }  # Return false if check succeeds for any combination
                         [>] .[1,0,2]   # Check whether b>a>c, that is b>a and c<a

Haskell , 50 octets

f[]=1<3
f(x:r)|(a,b)<-span(<x)r=all(>x)b&&f a&&f b

Essayez-le en ligne!

Scala ( 68 67 octets)

def%(i:Seq[Int])= !i.combinations(3).exists(c=>c(0)<c(1)&c(0)>c(2))

Essayez-le en ligne

Port of @ nwellnhof's answer .

Scala ( 122 103 octets)

def f(i:Seq[Int]):Boolean=if(i.size<1)1>0 else{val(s,t)=i.tail.span(_<i(0));t.forall(_>i(0))&f(s)&f(t)}

Merci à @Laikoni pour les suggestions visant à raccourcir les deux solutions.

Essayez-le en ligne

Explication:

1. couper (en utilisant Scala span) le tableau en utilisant la tête du tableau comme critère de découpage.
2. Confirmez que la première tranche du tableau est inférieure à la tête et que la deuxième tranche est supérieure à la tête.
3. vérifier récursivement que chaque tranche satisfait également (2)

05AB1E , 15 10 octets

ŒεD{3.IÊ}P

Réponse de Port of @Lynn 's Jelly .
-5 octets grâce à @Emigna .

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication: "

Π            # Take all sublists of the (implicit) input-list
              #  i.e. [2,3,1] → [[2],[2,3],[2,3,1],[3],[3,1],[1]]
              #  i.e. [1,2,3,4]
              #   → [[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4]]
 ε      }     # Map each to:
  D           #  Duplicate the current sublist on the stack
   {          #  Sort the copy
              #   i.e. [2,3,1] → [1,2,3]
              #   i.e. [2,3,4] → [2,3,4]
    3.I       #  Get the 4th (3rd 0-indexed) permutation of this list
              #   i.e. [1,2,3] → [2,3,1]
              #   i.e. [2,3,4] → [3,4,2]
       Ê      #  Check that the lists are NOT equal
              #   i.e. [2,3,1] and [2,3,1] → 0 (falsey)
              #   i.e. [2,3,4] and [3,4,2] → 1 (truthy)
         P    # Check whether all are truthy (and output implicitly)
              #  i.e. [1,1,0,1,1,1] → 0 (falsey)
              #  i.e. [1,1,1,1,1,1,1,1,1,1] → 1 (truthy)

Haskell , 41 octets

f(h:t)=t==[]||all(>h)(snd$span(<h)t)&&f t

Essayez-le en ligne!

Utilise l'observation de Lynn laquelle il suffit de vérifier qu'il n'y a pas de sous-séquence de for mid..high..low . Cela signifie que pour chaque élément h, la liste des éléments tqui suit est un bloc d'éléments <hsuivi d'un bloc d'éléments >h(les deux blocs peuvent être vides). Ainsi, le code vérifie que , après nous laissons tomber le préfixe des éléments <hdans t, les autres éléments sont tous >h. Récursif vérifie cela pour chaque élément initialh jusqu'à ce que la liste soit de longueur 1.

Une simplification potentielle est qu'il suffit de vérifier les sous-modèles mid..high, low où les deux derniers sont consécutifs. Malheureusement, Haskell n'a pas un moyen court d'extraire les deux derniers éléments, comme cela peut être fait de face avec une correspondance de modèle a:b:c. J'ai trouvé une solution plus courte qui vérifie les valeurs moyennes, élevées ... faibles , mais cela ne parvient pas à rejeter les entrées comme [3,1,4,2].

Cas de test formatés pris formatés de Laikoni .

Japt , 14 octets

d@sY ð_§XÃxÈ-Y

Interprète Japt

Les sorties false pour BST, truesans BST.

Explication:

d@                Run on each item X, return true if any aren't 0: 
  sY                  Ignore the numbers before this index
     ð_§XÃ            Get the indexes of numbers less than or equal to X
                          If it is a BST, this list will be e.g. [0,1,2...]
            -Y        Subtract the position within the index list from each index
                          eg. [0,1,2] -> [0,0,0] , [0,1,4] -> [0,0,2]
          xÈ          Sum the resulting array

Scala

Toutes les approches sont des implémentations de la règle indiquée par tsh.

109

l.zipWithIndex.foldLeft(1>0){case(r,(v,i))=>r&l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)}

101

(for(i<-l.indices)yield l.zip(l.tail).slice(i+1,l.size).forall(x =>l(i)>x._1|l(i)<x._2)).forall(x=>x)

98

l.indices.foldLeft(1>0)((r,i)=>r&(l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)))

78

(for(i<-l.indices;j<-i+1 to l.size-2)yield l(i)>l(j)|l(i)<l(j+1)).forall(x=>x)

Si ce doit être une fonction et pas seulement une expression, alors chaque ligne doit commencer par (17 octets)

def%(l:Seq[Int])=

Oracle SQL, 177 octets

with r(i,v)as(select rownum,value(t)from table(a)t)
select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,(select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i

Puisqu'il n'y a pas de type booléen dans Oracle SQL, la requête renvoie 1 ou 0.

Oracle SQL 12c, 210 octets

with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)from(select value(t)c from table(powermultiset_by_cardinality(a,3))t)

Il n'est pas possible d'accéder à l'élément du tableau en SQL de la même manière qu'en PL / SQL - c'est-à-dire a (i), donc la fonction a fété déclarée dans with clausece but. Sinon, la solution aurait été beaucoup plus courte.

Autres limitations

• lève une exception pour les tableaux de moins de 3 éléments (au lieu de renvoyer 1)
• il y a une hypothèse que powermultiset_by_cardinality préserve l'ordre même si ce n'est pas explicitement indiqué dans la documentation

sqlplus listing

SQL> set heading off
SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(6,3,2,4,5,1,8,7,9))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /

                                            0

SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(6,3,2,4,5,1,8,7,9),3))t)
  4  /

                                                     0

SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(8,3,1,6,4,7,10,14,13))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /

                                            1

SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(8,3,1,6,4,7,10,14,13),3))t)
  4  /

                                                     1

Vérification en ligne apex.oracle.com

Mise à jour

Oracle SQL, 155 octets

with r(i,v)as(select rownum,value(t)from table(a)t)select nvl(min(case when a.v<b.v and a.v>c.v then 0end),1)r from r a,r b,r c where a.i<b.i and b.i+1=c.i

C, 823 octets (sans compter les espaces blancs); 923 octets (y compris les espaces blancs)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{struct tree * left;struct tree * right;int val;}tree;static int * test_p = 0;
void insert_root(tree ** root, int in)
{if (*root == NULL){*root = (tree *)calloc(1,sizeof(tree));(*root)->val = in;return;}else if (in < (*root)->val){insert_root(&((*root)->left),in);}else{insert_root(&((*root)->right),in);}}
void preorder(tree * root)
{if ( root == 0x0 ) { return; }*test_p++ = root->val;preorder(root->left);preorder(root->right);}
int main(int argc, char ** argv)
{int test_list[argc-1];memset(test_list,0,argc*sizeof(int));test_p = test_list;tree * root = (tree *)calloc(1,sizeof(tree));root->val = strtol(argv[1],0x0,10);int i = 1;while ( argv[++i] != 0x0 ){insert_root(&root,strtol(argv[i],0x0,10));}preorder(root);test_p = test_list;i = 1;while ( ( i < argc ) ){if ( *test_p != strtol(argv[i],0x0,10) ){return 0;}test_p++;i++;}return 1;}

La version lisible du programme est ci-dessous:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tree
{
    struct tree * left;

    struct tree * right;

    int val;

} tree;


static int * test_p = 0;

void insert_root(tree ** root, int in)
{
  if (*root == NULL)
  {
    *root = (tree *)calloc(1,sizeof(tree));

    (*root)->val = in;

    return;
  }

  else if (in < (*root)->val)
  {
    insert_root(&((*root)->left),in);
  }

  else
  {
    insert_root(&((*root)->right),in);
  }
}

void preorder(tree * root)
{
    if ( root == 0x0 ) {  return; }

        *test_p++ = root->val;

        preorder(root->left);

        preorder(root->right);

}

int main(int argc, char ** argv)
{
    int test_list[argc-1];

    memset(test_list,0,argc*sizeof(int));

    test_p = test_list;

    tree * root = (tree *)calloc(1,sizeof(tree));

    root->val = strtol(argv[1],0x0,10);

    int i = 1;

    while ( argv[++i] != 0x0 )
    {
        insert_root(&root,strtol(argv[i],0x0,10));
    }

    preorder(root);

    test_p = test_list;

    i = 1;

    while ( ( i < argc ) )
    {
        if ( *test_p != strtol(argv[i],0x0,10) )
        {
            return 0;
        }

        test_p++;

        i++;
    }

    return 1;   
}

La méthode principale de ce programme lit la liste des numéros qui sont (prétendument) une traversée de précommande légitime.

La fonction insert_root qui est appelée insère les entiers dans une arborescence de recherche binaire où les nœuds précédents contiennent des valeurs moindres et les nœuds suivants contiennent des valeurs int plus grandes.

La fonction de précommande (racine) parcourt l'arborescence dans une traversée de précommande et concatène simultanément chaque entier que l'algorithme rencontre dans la liste int test_list .

Une dernière boucle while teste si chacune des valeurs int de la liste stdin et celles de test_list sont équivalentes à chaque index. S'il existe un élément de liste de stdin qui ne correspond pas à l'élément correspondant dans test_list à l'index respectif, la fonction principale renvoie 0. Sinon, la méthode principale renvoie 1 .

Pour déterminer ce qui est retourné, tapez echo $ status dans le terminal bash. BASH imprime un 1 ou un 0.