Zwiększająca sekwencję zestawów

11

tło

Ex zwiększenie ustalonej kolejności kolejnością określa się jako sekwencję zestawów całkowitą który spełnia następujące:NS1,S2,,Sn

  • Każdy jest niepustym podzbiorem .Si{1,2,,N}
  • Dla , , tj. dwa kolejne zestawy nie mają wspólnych elementów.1i<nS.jaS.ja+1=
  • Dla średnia (wartość średnia) jest ściśle mniejsza niż .1ja<nS.jaS.ja+1

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą N, wyprowadza długość najdłuższej, rosnącej sekwencji sekwencji N.

Przypadki testowe

Są one oparte na wynikach Project Euler użytkownika 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

Zasady

Obowiązują standardowe zasady . Najkrótsze prawidłowe przesłanie w bajtach wygrywa.

Hojność

Problem ten był omawiany tutaj na forum projektu Euler około 4 lata temu, ale nie udało nam się opracować sprawdzalnego algorytmu czasu wielomianowego (pod względem N). Dlatego przyznam +200 nagród za pierwsze zgłoszenie, które to osiągnie, lub udowodnię jego niemożliwość.

Bubbler
źródło
Spędziłem ponad tydzień próbując wymyślić algorytm czasu wielomianowego lub dowód twardości NP przy użyciu redukcji. Czy ktoś tu poczynił jakieś postępy?
Enrico Borba,

Odpowiedzi:

4

Brachylog , 28 bajtów

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

Wypróbuj online!

To jest naprawdę cholernie wolne. Trwa około 30 sekund dla N = 3i nie zakończyło się po 12 minutach dla N = 4.

Wyjaśnienie

⟦₁                             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.

Szybsza wersja, 39 bajtów

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

To zajmuje około 50 sekund na moim komputerze N = 4.

Jest to ten sam program, z wyjątkiem tego, że sortujemy podzbiór podzbiorów według średniej zamiast losowej permutacji. Więc używamy {⟨+/l⟩/₁/₁}ᵒzamiast p.

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

Musimy uzyskać średnią zmiennoprzecinkową, ponieważ właśnie odkryłem niedorzeczny błąd, w którym zmiennoprzecinkowe i liczby całkowite nie porównują wartości, ale według typu z predykatami porządkowania (dlatego też używam <ᵈi nie <₁porównuję obu średnich; to drugie wymagałoby tego sztuczka podwójnej inwersji do pracy).

Fatalizować
źródło
Planowałem powoli zająć się tym problemem (odkąd @JonathanAllan wspomniał o tym w innym komentarzu), ale prawdopodobnie mam tygodnie, by wymyślić coś takiego! Podoba mi się, jak (jak większość odpowiedzi Brachylog) na końcu wygląda po prostu na porządne powtórzenie samego pytania.
Sundar - Przywróć Monikę
@sundar zawsze możesz do niej wrócić później i spróbować odkryć rozwiązanie!
Fatalize
3

CJam (81 bajtów)

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

Demo online . Powinien zostać wykonany dla danych wejściowych 4w rozsądnym czasie, ale nie spróbowałbym tego przy wyższych danych wejściowych.

Sekcja

{                 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
}
Peter Taylor
źródło
1

JavaScript (ES6), 175 bajtów

Naiwne i raczej powolne wyszukiwanie rekurencyjne. Obliczenie 7 pierwszych warunków w TIO zajmuje około 15 sekund.

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

Wypróbuj online!

lub przetestuj tę zmodyfikowaną wersję, która generuje najdłuższą sekwencję ex-rosnącą.

W jaki sposób?

{1,2),,n}za

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

Część rekurencyjna:

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()
Arnauld
źródło
1

Python 3 , 205 197 184 182 bajtów

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*

Wypróbuj online!

Jonathan Frech
źródło
197 bajtów używając sumzamiast chain.from_iterable.
ovs
@ceilingcat Dziękuję.
Jonathan Frech,