Contexte

Une séquence d'ensemble ex-croissante d'ordre est définie comme une séquence d'ensembles entiers qui satisfait les conditions suivantes:S 1 , S 2 , ⋯ , S $N$$S_1,S_2,\cdots,S_n$

• Chaque est un sous-ensemble non vide de . { 1 , 2 , ⋯ , N $S_i$$\{1,2,\cdots,N\}$
• Pour , , c'est-à-dire que deux ensembles consécutifs quelconques n'ont aucun élément en commun.S i ∩ S i + 1 = $1\le i<n$$S_i \cap S_{i+1} = \varnothing$
• Pour , la moyenne (valeur moyenne) de est strictement inférieure à celle de .S i S i + $1\le i<n$$S_i$$S_{i+1}$

Défi

Étant donné un nombre entier positif N, affichez la longueur de la plus longue séquence d'ensemble d'ex-ordre croissant N.

Cas de test

Ceux-ci sont basés sur les résultats de l'utilisateur de Project Euler thundre .

1 => 1 // {1}
2 => 2 // {1} {2}
3 => 3 // {1} {2} {3}
4 => 5 // {1} {2} {1,4} {3} {4}
5 => 7 // {1} {2} {1,4} {3} {2,5} {4} {5}
6 => 10 // {1} {2} {1,4} {3} {1,4,5} {2,3,6} {4} {3,6} {5} {6}
7 => 15 // {1} {2} {1,4} {3} {1,2,7} {3,4} {1,2,5,7} {4} {1,3,6,7} {4,5} {1,6,7} {5} {4,7} {6} {7}
8 => 21
9 => 29
10 => 39
11 => 49
12 => 63
13 => 79
14 => 99
15 => 121
16 => 145
17 => 171
18 => 203
19 => 237
20 => 277
21 => 321
22 => 369
23 => 419
24 => 477
25 => 537

Règles

Les règles de code-golf standard s'appliquent. La soumission valide la plus courte en octets l'emporte.

Prime

Ce problème a été discuté ici sur le forum Project Euler il y a environ 4 ans, mais nous n'avons pas réussi à trouver un algorithme à temps polynomial prouvable (en termes de N). Par conséquent, j'accorderai +200 primes à la première soumission qui y parviendra ou prouverai son impossibilité.

Brachylog , 28 octets

⟦₁⊇ᶠk⊇pSs₂ᶠ{c≠&⟨+/l⟩ᵐ<ᵈ}ᵐ∧Sl

Essayez-le en ligne!

C'est vraiment très lent. N = 3Cela prend environ 30 secondes et il ne s'est pas terminé après 12 minutes N = 4.

Explication

⟦₁                             Take the range [1, …, Input]
  ⊇ᶠk                          Find all ordered subsets of that range, minus the empty set
     ⊇                         Take an ordered subset of these subsets
      pS                       Take a permutation of that subset and call it S
       Ss₂ᶠ                    Find all substrings of 2 consecutive elements in S
           {           }ᵐ      Map for each of these substrings:
            c≠                   All elements from both sets must be different
              &⟨+/l⟩ᵐ            And the average of both sets (⟨xyz⟩ is a fork like in APL)
                     <ᵈ          Must be in strictly increasing order
                         ∧Sl   If all of this succeeds, the output is the length of L.

Version plus rapide, 39 octets

⟦₁⊇ᶠk⊇{⟨+/l⟩/₁/₁}ᵒSs₂ᶠ{c≠&⟨+/l⟩ᵐ<₁}ᵐ∧Sl

Cela prend environ 50 secondes sur mon ordinateur pendant N = 4.

C'est le même programme, sauf que nous trions le sous-ensemble de sous-ensembles par moyenne au lieu de prendre une permutation aléatoire. Nous utilisons donc {⟨+/l⟩/₁/₁}ᵒau lieu de p.

{         }ᵒ     Order by:
 ⟨+/l⟩             Average (fork of sum-divide-length)
      /₁/₁         Invert the average twice; this is used to get a float average

Nous devons obtenir une moyenne flottante car je viens de découvrir un bug ridicule dans lequel les flottants et les entiers ne se comparent pas par valeur mais par type avec des prédicats de commande (c'est aussi pourquoi j'utilise <ᵈet non pas <₁pour comparer les deux moyennes; ce dernier nécessiterait que double astuce d'inversion pour travailler).

CJam (81 octets)

{YY@#(#{{2bW%ee{)*~}%}:Z~{)Z__1b\,d/\a+}%$}%{_,1>{2ew{z~~&!\~=>}%0&!}{,}?},:,:e>}

Démo en ligne . Il devrait s'exécuter pour l'entrée 4dans un délai raisonnable, mais je ne l'essayerais pas avec des entrées plus élevées.

Dissection

{                 e# Declare a block (anonymous function)
  YY@#(#          e# There are 2^N subsets of [0, N), but the empty subset is problematic
                  e# so we calculate 2^(2^N - 1) subsets of the non-empty subsets
  {               e# Map integer to subset of non-empty subsets:
    {             e#   Define a block to map an bitset to its set indices; e.g. 9 => [0 3]
      2bW%ee      e#     Convert to base 2, reverse, and index
      {)*~}%      e#     If the bit was set, keep the index
    }:Z           e#   Assign the block to variable Z
    ~             e#   Evaluate it
    {             e#   Map those indices to non-empty subsets of [0, N):
      )Z          e#     Increment (to skip the empty set) and apply Z
      __1b\,d/    e#     Sum one copy, take length of another, divide for average
      \a+         e#     Wrap the subset and prepend its average value
    }%
    $             e#   Sort (lexicographically, so by average value)
  }%
  {               e# Filter out subsets of subsets with conflicts:
    _,1>{         e#   If the length is greater than 1
      2ew         e#     Take each consecutive pair of subsets
      {           e#     Map:
        z~        e#       Zip and expand to get [score1 score2] [subset1 subset2]
        ~&!\      e#       No element in common => 1
        ~=        e#       Different scores => 0
        >         e#       1 iff both constraints are met
      }%
      0&!         e#     1 iff no consecutive pair failed the test
    }{
      ,           e#   Otherwise filter to those of length 1
    }?
  },
  :,:e>           e# Map to size of subset and take the greatest
}

JavaScript (ES6), 175 octets

Une recherche récursive naïve et assez lente. Prend environ 15 secondes pour calculer les 7 premiers termes sur TIO.

n=>(a=[...Array(n)].reduce(a=>[...a,...a.map(y=>[x,...y],x=n--)],[[]]),g=(p,b=a,n)=>a.map(a=>(m=a.map(n=>s+=++k*b.includes(n)?g:n,s=k=0)&&s/k)>p&&g(m,a,-~n),r=r>n?r:n))(r=0)|r

Essayez-le en ligne!

ou testez cette version modifiée qui produit la plus longue séquence de jeu ex-croissante.

Comment?

Nous calculons d'abord l'ensemble de puissance de et le stockons dans :$\{1,2,\dots,n\}$$a$

a = [...Array(n)].reduce(a =>
  [...a, ...a.map(y => [x, ...y], x = n--)],
  [[]]
)

Partie récursive:

g = (                         // g = recursive function taking:
  p,                          //   p = previous mean average
  b = a,                      //   b = previous set
  n                           //   n = sequence length
) =>                          //
  a.map(a =>                  // for each set a[] in a[]:
    (m = a.map(n =>           //   for each value n in a[]:
      s +=                    //     update s:
        ++k * b.includes(n) ? //       increment k; if n exists in b[]:
          g                   //         invalidate the result (string / integer --> NaN)
        :                     //       else:
          n,                  //         add n to s
      s = k = 0)              //     start with s = k = 0; end of inner map()
      && s / k                //   m = s / k = new mean average
    ) > p                     //   if it's greater than the previous one,
    && g(m, a, -~n),          //   do a recursive call with (m, a, n + 1)
    r = r > n ? r : n         //   keep track of the greatest length in r = max(r, n)
  )                           // end of outer map()

Python 3 , 205 197 184 184 182 octets

• Enregistré huit vingt et un octets grâce aux ovs .
• Enregistré deux octets grâce à ce plafond .

f=lambda N,c=[[1]]:max([len(c)]+[f(N,c+[n])for k in range(N)for n in combinations(range(1,N+1),k+1)if not{*c[-1]}&{*n}and sum(c[-1])/len(c[-1])<sum(n)/len(n)]);from itertools import*

Essayez-le en ligne!