Rozważ tablicę Adługości n. Tablica zawiera tylko dodatnie liczby całkowite. Na przykład A = (1,1,2,2). Zdefiniujmy f(A)jako zbiór sum wszystkich niepustych, sąsiadujących pod-macierzy A. W tym przypadku f(A) = {1,2,3,4,5,6}. Kroki do produkcji f(A) są następujące:

Podziemne Asą (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Ich odpowiednie kwoty to 1,1,2,2,2,3,4,4,5,6. Zestaw, który otrzymujesz z tej listy, jest zatem {1,2,3,4,5,6}.

Zadanie

Biorąc pod uwagę zestaw sum Spodanych w posortowanej kolejności, zawierający tylko dodatnie liczby całkowite i długość tablicy n, Twoim zadaniem jest wyprowadzenie co najmniej jednej Xtakiej tablicy f(X) = S.

Na przykład, jeśli S = {1,2,3,5,6}i n = 3wtedy poprawnym wynikiem jest X = (1,2,3).

Jeśli nie ma takiej tablicy, Xkod powinien wypisać dowolną stałą wartość.

Przykłady

Wejście:, n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13)możliwe wyjście:X = (3, 5, 1, 4)

Wejście:, n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)możliwe wyjście:X = (5, 3, 2, 2, 5, 5)

Wejście:, n=6, S = (2, 4, 6, 8, 10, 12, 16)możliwe wyjście:X = (4, 2, 2, 2, 2, 4)

Wejście:, n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14)możliwe wyjście:X = (4, 2, 1, 1, 2, 4)

Wejście: n=10, S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)możliwe wyjścia: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5).

Wejście: n=15, S = (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)możliwe wyjścia: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3).

Format wejściowy i wyjściowy

Twój kod może pobierać dane wejściowe i generować dane wyjściowe w dowolnym, łatwym dla człowieka formacie, który uważasz za dogodny. Proszę jednak pokazać wyniki testowania na przykładach w pytaniu.

Czas trwania

Musisz być w stanie uruchomić kod do końca dla wszystkich przykładów w pytaniu. Zasadniczo powinno to być poprawne n, 15ale nie trzeba udowadniać, że byłoby wystarczająco szybkie dla wszystkich danych wejściowych.

Łuska , 20 bajtów

ḟȯ⁰¦ṁ∫ṫ!¡Sof~Λ€∫×:¹g

Wypróbuj online!

Zwraca jedno rozwiązanie lub pustą listę, jeśli nie istnieje. Ostatni przypadek testowy ( n=15) kończy się w TIO w 3,8 sekundy.

Wyjaśnienie

Program składa się z dwóch części. W pierwszej części ( ¡i po jej prawej stronie) tworzymy nieskończoną listę, której kelementem jest lista zawierająca wszystkie listy długości, w kktórych znajdują się sumy plasterków S. Robimy to indukcyjnie, zaczynając od 1-elementowych wycinków Si na każdym kroku poprzedzając każdy element Sdo każdej listy i zachowując te, których sumy prefiksów są w środku S. W drugiej części ( !i po lewej stronie) bierzemy nelement th listy, który zawiera nlisty długości . Spośród nich wybieramy pierwszy, którego sumy plasterków faktycznie zawierają każdy element S.

W kodzie najpierw zamieńmy oi ȯ(które składają się z dwóch i trzech funkcji w jedną) nawiasy dla zachowania przejrzystości.

¡S(f~Λ€∫)×:¹g  First part. Input is a list, say S=[1,2,3]
            g  Group equal adjacent elements: [[1],[2],[3]]
¡              Iterate function:
                Argument is a list of lists, say [[1,1],[1,2],[2,1]]
         ×      Mix (combine two lists in all possible ways)
          :     by prepending
           ¹    with the list S: [[1,1,1],[1,1,2],[2,1,1],[1,2,1],[2,1,2],[3,1,1],[2,2,1],[3,1,2],[3,2,1]]
   f            Filter by condition:
        ∫        Cumulative sums: [[1,2,3],[1,2,4],[2,3,4],[1,3,4],[2,3,5],[3,4,5],[2,4,5],[3,4,6],[3,5,6]]
     ~Λ          All of the numbers
 S     €         are elements of S: [[1,1,1]]
                 Only this list remains, since the other cumulative sums contain numbers not from S.
               Result of iteration: [[[1],[2],[3]],[[1,1],[1,2],[2,1]],[[1,1,1]],[],[],[]...

ḟ(⁰¦ṁ∫ṫ)!      Second part. Implicit input, say n=2.
        !      Take nth element of above list: [[1,1],[1,2],[2,1]]
ḟ              Find first element that satisfies this:
                Argument is a list, say [1,2]
      ṫ         Tails: [[1,2],[2]]
    ṁ           Map and concatenate
     ∫          cumulative sums: [1,3,2]
 ȯ ¦            Does it contain all elements of
  ⁰             S? Yes.
               Result is [1,2], print implicitly.

Niektóre części wymagają wyjaśnienia. W tym programie ⁰¹oba indeksy górne odnoszą się do pierwszego argumentu S. Jeśli jednak αjest funkcją, α¹oznacza to „zastosuj αdo S”, a ⁰αoznacza „podłącz Sdo drugiego argumentu α”. Funkcja ¦sprawdza, czy jej pierwszy argument zawiera wszystkie elementy drugiego (liczenie krotności), więc Spowinien być drugim argumentem.

W pierwszej części ¡używaną funkcję można interpretować jako S(f~Λ€∫)(×:)¹. Kombinator Szachowuje się jak Sαβγ -> (αγ)(βγ), co oznacza, że ​​możemy go uprościć (f~Λ€∫¹)(×:¹). Druga część ×:¹to „łączenie z Sprzygotowaniem”, a jej wynik jest przekazywany do pierwszej części. Pierwsza część f~Λ€∫¹działa w ten sposób. Funkcja ffiltruje listę według warunku, którym w tym przypadku jest ~Λ€∫¹. Otrzymuje listę list L, więc mamy ~Λ€∫¹L. Kombinator ~zachowuje się tak ~αβγδε -> α(βδ)(γε): pierwszy argument jest przekazywany do β, drugi do γ, a wyniki są łączone z α. Oznacza to, że mamy Λ(€¹)(∫L). Ostatnia część ∫Lto tylko skumulowane sumy L,€¹jest funkcją, która sprawdza członkostwo Si Λprzyjmuje warunek (tutaj €¹) oraz listę (tutaj ∫L) i sprawdza, czy wszystkie elementy go spełniają. Mówiąc najprościej, filtrujemy wyniki mieszania według tego, czy są w nich sumy skumulowane S.

Rubin , 135 bajtów

->a,n{r=w=1;r+=1until w=(s=a[0,r]).product(*[s]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Wypróbuj online!

Skorzystaj z pierwszego wyszukiwania. n = 10 działa na TIO, n = 15 zajmuje więcej niż minutę, ale działa na moim komputerze.

Rubinowy , 147 bajtów

->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product(*[s=a[0,r]]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Wypróbuj online!

Wersja zoptymalizowana, działa na TIO przez n = 15 (~ 20 sekund)

W rzeczywistości jest to początek podejścia bez użycia siły. Mam nadzieję, że ktoś nad tym popracuje i znajdzie kompletne rozwiązanie.

Pierwsze pomysły:

• Suma tablicy wyjściowej jest ostatnim elementem (maks.) Tablicy wejściowej.
• Suma tablicy wyjściowej minus pierwszy (lub ostatni) element jest drugim ostatnim elementem tablicy wejściowej.
• Jeśli tablica jest rozwiązaniem, to tablica odwrotna również jest rozwiązaniem, więc możemy założyć, że pierwszy element jest różnicą między dwoma ostatnimi elementami tablicy wejściowej.
• Drugi element może być różnicą między drugim a trzecim lub drugim i czwartym ostatnim elementem tablicy wejściowej.

Co prowadzi nas do kolejnej optymalizacji:

Rubinowy , 175 bajtów

->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product([a[-2]-a[-3],a[-2]-a[-4]],*[s=a[0,r]]*(n-2)).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Wypróbuj online!

~ 8,5 sekundy w TIO. Nie jest zły...

... i tak dalej (do wdrożenia)

Haskell, 117 111 bajtów

6 bajtów zapisanych dzięki @nimi!

f r i n s|n<1=[r|r==[]]|1<2=[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
n&s=f s[]n s

Wypróbuj online!

fr$S$ins

Kiedy nzero (gra w golfa n<1), lista musi być gotowa, więc sprawdzamy, czy wszystkie wartości zostały zauważone. Jeśli nie, zwracamy pustą listę, aby wskazać brak rozwiązań, w przeciwnym razie zwracamy listę singletonów zawierającą pustą listę, do której wybrane elementy zostaną dodane. Przypadek ten można również rozwiązać za pomocą dodatkowych równań

f [] _ 0 _=[[]]
f _ _ 0 _=[]

Jeśli nnie jest zero, wracamy

[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
 ^1^ ^2^^ ^......3......^ ^.....4.....^ ^.............5.............^

Jest to lista (1) list, z których pochodzi pierwszy element (2), sa reszta (5) pochodzi z wywołania rekurencyjnego, pod warunkiem (4), że są wszystkie nowe sumy s. Nowe sumy są obliczane w (3) - uwaga tpochodzi z listy singletonów, brzydkiego golfowego hacka dla tego, co w idiomatycznym Haskell byłoby let t=y:map(y+)i. Wywołanie rekurencyjne (5) otrzymuje jako nowy rzestaw stary bez tych elementów, które pojawiają się wśród nowych sum t.

Główna funkcja &wywołuje funkcję pomocnika, mówiąc, że wciąż musimy zobaczyć wszystkie wartości ( r=s) i że nie ma jeszcze żadnych sum (i=[] ).

W przypadku siedmiu kolejnych bajtów możemy ograniczyć obliczenia, aby dać tylko pierwszy wynik (jeśli istnieje), który jest znacznie szybszy i obsługuje wszystkie przypadki testowe w mniej niż 2 sekundy.

Wypróbuj online! (jest to pierwszy wariant tylko starej wersji starej wersji)

Czysty , 177 bajtów

import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(?{#u\\u<-s|u<=(last s)-n}(last s)n)
?e s n|n>1=[[h:t]\\h<-:e|h<=s-n,t<- ?e(s-h)(n-1)]=[[s]]

Wypróbuj online!

n=15Sprawa testowa zajmuje około 40 sekund na moim komputerze , ale limit czasu dla TIO.

Czysty , 297 bajtów

import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(~[u\\u<-s|u<=(last s)-n](last s)n(reverse s))
~e s n a|n>4=let u=a!!0-a!!1 in[[u,h:t]\\h<-[a!!1-a!!2,a!!1-a!!3],t<- ?e(s-u-h)(n-2)]= ?e s n
?e s n|n>1=[[h:t]\\h<-e,t<- ?(takeWhile((>=)(s-n-h))e)(s-h)(n-1)]=[[s]]

Wypróbuj online!

Ten zawiera kilka optymalizacji wykonanych przez GB a także niektóre własne. Myślę, że kilka z nich może być bardziej ogólnych, więc dodam wyjaśnienie, kiedy to się skończy.

Na moim komputerze zajmuje to około 10 sekund, a TIO - 40 sekund.

Python 3 , 177 bajtów

from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):
  a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];
  {sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)

Wypróbuj online!

(dodano kilka nowych linii / spacji, aby uniknąć konieczności przewijania kodu przez czytelników)

Bezpośredni port mojej odpowiedzi Jelly (z pewnymi modyfikacjami, patrz sekcja „uwaga” poniżej)

Lokalny wynik uruchomienia:

[user202729@archlinux golf]$ printf '%s' "from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];{sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)" > a.py
[user202729@archlinux golf]$ wc -c a.py
177 a.py
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25], 10)' 2>/dev/null
[1, 4, 1, 1, 1, 1, 1, 7, 7, 1]

real    0m3.125s
user    0m3.119s
sys     0m0.004s
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31], 15)' 2>/dev/null
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]

real    11m36.093s
user    11m33.941s
sys     0m0.387s
[user202729@archlinux golf]$ 

Słyszałem, że itertoolsjest to pełne, ale moja najlepsza combinationsimplementacja jest jeszcze bardziej szczegółowa:

c=lambda s,n,p:s and c(s[1:],n-1,p+s[:1])+c(s[1:],n,p)or[]if n else[p]

Uwaga .

• Użycie podziału / modulo w a[p//n:p%n+1]zajmuje około 2x dłużej, ale oszczędza niektóre bajty.
• To trochę różni się od odpowiedzi Jelly - odpowiedź Jelly iteruje się wstecz.
• Dzięki combinationszwróceniu iteratora jest to bardziej przyjazne dla pamięci.

Galaretka , 35 bajtów

Ẇ§QṢ⁼³
;³ṫ-¤0;I
ṖṖœcƓ_2¤¹Ṫ©ÇѬƲ¿ṛ®Ç

Wypróbuj online!

Uruchom lokalnie: (n = 15 zajmuje więcej niż 1 GB pamięci RAM)

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,23,24,25]'<<<10
[8, 6, 2, 1, 1, 1, 1, 3, 1, 1]
real    0m1.177s
user    0m0.000s
sys     0m0.015s

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 2
6, 27, 28, 30, 31]'<<<15
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]
real    12m24.488s
user    0m0.000s
sys     0m0.015s

(faktycznie uruchomiłem wersję zakodowaną w UTF8, która zajmuje więcej niż 35 bajtów, ale wynik jest taki sam)

To rozwiązanie wykorzystuje zwarcie w celu skrócenia czasu pracy.

$\binom {|S|-2}{n-2} \times \left( \frac {n^3}6 + n^2\log{n^2} \right)$$\binom {26-2}{15-2} \times \left( \frac {15^3}6 + 15^2\log{15^2} \right) \approx 5.79 \times 10^9$ , jednak ze względu na nieefektywność Pythona i galaretki ukończenie tego zajmuje wieczność. Dzięki zwarciu może zakończyć się znacznie wcześniej.

Wyjaśnienie

Zauważamy, że sumy wszystkich niepustych prefiksów są obecne na wejściu i ściśle się zwiększają. Możemy również założyć, że największy i drugi co do wielkości element jest sumą prefiksu.

Dlatego możemy rozważyć wszystkie sposoby wyboru $n-2$ odrębne elementy od pierwszego $|S|-2$ elementy (są $\binom {|S|-2}{n-2}$takie listy), oblicz kolejne różnice w celu odzyskania elementów; następnie sprawdź, czy jest ważna naiwnie (zdobądź wszystko$n^2$podzakresy, oblicz sumę, unikaj. Całkowita długość subarrays wynosi około$n^3 \over 6$)

Nie przetestowane (ale powinny mieć identyczną wydajność)

Galaretka , 32 bajty

Ṫ©ÑẆ§QṢ⁻³
;³ṫ-¤ŻI
ṖṖœcƓ_2¤¹Ñ¿ṛ®Ç

Wypróbuj online!

Bardziej nieefektywna wersja (bez zwarcia):

Galaretka , 27 bajtów

Ẇ§QṢ⁼³
ṖṖœcƓ_2¤µ;³ṫ-¤0;I)ÑƇ

Wypróbuj online!

W przypadku testu n = 15 zajmuje do 2 GB pamięci RAM i nie kończy się po ~ 37 minutach.

Uwaga : Ẇ§można zastąpić ÄÐƤẎ. Może być bardziej wydajny.

APL (NARS), znaki 758, bajty 1516

r←H w;i;k;a;m;j
   r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k

G←{H⍵[⍋⍵]}

r←a d w;i;j;k;b;c
   k←↑⍴w ⋄b←⍬⋄r←0 ⋄j←¯1
A: i←1⋄j+←1⋄→V×⍳(i+j)>k
B: →A×⍳(i+j)>k⋄c←+/w[i..(i+j)]⋄→0×⍳∼c∊a⋄→C×⍳c∊b⋄b←b,c
C: i+←1⋄→B
V: →0×⍳∼a⊆b
   r←1

r←a F w;k;j;b;m;i;q;x;y;c;ii;kk;v;l;l1;i1;v1
   w←w[⍋w]⋄r←a⍴w[1]⋄l←↑⍴w⋄k←w[l]⋄m←8⌊a-2⋄b←¯1+(11 1‼m)⋄j←2⋄i←1⋄x←↑⍴b⋄i1←0⋄v1←⍬
I: i1+←1⋄l1←w[l]-w[l-i1]⋄v1←v1,w[1+l-i1]-w[l-i1]⋄→I×⍳(l1=i1)∧l>i1⋄→B
E: r←,¯1⋄→0
F: i←1⋄q←((1+(a-2)-m)⍴0),(m⍴1),0⋄r+←q
A:   i+←1⋄j+←1⋄→E×⍳j>4000
B:   →F×⍳i>x⋄q←((1+(a-2)-m)⍴0),b[i;],0⋄q+←r⋄v←q[1..(a-1)]⋄→A×⍳0>k-y←+/v
   q[a]←k-y⋄→A×⍳l1<q[a]⋄→A×⍳∼q⊆w⋄→A×⍳∼l1∊q⋄→A×⍳∼v1⊆⍦q⋄c←G q∼⍦v1⋄ii←1⋄kk←↑⍴c⋄→D
C:   →Z×⍳w d v1,ii⊃c⋄ii+←1
D:   →C×⍳ii≤kk
   →A
Z: r←v1,ii⊃c

Funkcja G w G x (za pomocą funkcji H) znajdowałaby wszystkie permutacje x. Funkcja d w xdy sprawdza, czy tablica y generuje po tablicy ćwiczeń x zwracając wartość logiczną. Funkcja F w x F y zwróci tablicę r o długości x, tak że ydr jest prawdą (= 1) Trochę dłuższa niż implementacja, ale to ta, która oblicza wszystkie przypadki w teście mniej czasu ... Ostatni przypadek dla n = 15 działa tylko 20 sekund ... muszę powiedzieć, że nie znajduje wielu rozwiązań, zwraca tylko jedno rozwiązanie (w końcu wydaje się, że tak) w krótszym czasie (niezbadany test dla różnych danych wejściowych ...) 16 + 39 + 42 + 8 + 11 + 11 + 18 + 24 + 24 + 54 + 11 + 12 + 7 + 45 + 79 + 69 + 12 + 38 + 26 + 72 + 79 + 27 + 15 + 6 + 13 (758)

  6 F (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)
5 3 2 2 5 5 
  6 F (2, 4, 6, 8, 10, 12, 16)
4 2 2 2 2 4 
  6 F (1, 2, 3, 4, 6, 7, 8, 10, 14)
4 2 1 1 2 4 
  10 F (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
1 1 3 1 2 3 5 1 3 5 
  15 F (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)
1 2 1 3 3 1 3 3 1 3 3 1 2 1 3 
  ww←(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
  ww≡dx 1 1 3 1 2 3 5 1 3 5 
1