Iterowane sumy częściowe

23

Częściowe sumy listy liczb całkowitych [a 1 , a 2 , a 3 , ..., a n ] są

s 1 = a 1
s 2 = a 1 + a 2
s 3 = a 1 + a 2 + a 3
...
s n = a 1 + a 2 + ... + a n n

Następnie możemy pobrać listę sum częściowych [s 1 , s 2 , s 3 , ..., s n ] i ponownie obliczyć jej sumy częściowe, aby utworzyć nową listę i tak dalej.

Powiązane: Iterowane różnice w przód

Wkład:

  • Niepusta lista liczb całkowitych
  • Dodatnia liczba iteracji,

Dane wyjściowe: wydrukuj lub zwróć listę liczb całkowitych, która wynika z wielokrotnego pobrania sum częściowych.

Wygrywa najmniej bajtów. Wbudowane są OK, nawet jeśli bezpośrednio rozwiązują problem.

Przypadki testowe:

f([-3, 4, 7, -1, 15], 1) == [-3, 1, 8, 7, 22]
f([-3, 4, 7, -1, 15], 3) == [-3, -5, 1, 14, 49]

Tabela liderów:

Pokaż fragment kodu

code-golf number arithmetic sequence array-manipulation xnor
źródło
Czy argumenty muszą być w tej samej kolejności, czy też liczba iteracji może występować przed listą liczb?
kirbyfan64sos
@ kirbyfan64sos Każde zamówienie.
xnor

Odpowiedzi:

14

J, 5 bajtów

+/\^:

Spróbuj go w Internecie na J.js .

Jak to działa

  • /\ to przysłówek (funkcja, która przyjmuje lewy argument), który łącznie zmniejsza się o swój argument.

  • Zatem +/\jest skumulowana suma czasownik.

  • ^:jest koniunkcją mocy ; (f ^: n) ystosuje fsię ogółem ndo y.

  • Pociąg koniunkcji czasownika +/\^:tworzy przysłówek, który powtarza się +/\tyle razy, ile podano w (lewym) argumencie.

    x (+/\^:) yzostanie sparsowany jako (x (+/\^:)) y, co jest równoważne z wykonaniem (+/\^:x) y.

Dzięki @Zgarb za pomoc w wyjaśnieniu.

Dennis
źródło
13

Mathematica, 19 bajtów

Cóż, jeśli wbudowane są w porządku ...

Accumulate~Nest~##&

Definiuje funkcję o takim samym podpisie jak przykłady w wyzwaniu. Jestem całkiem pewny, dzięki długiej nazwie, Accumulateże będzie to łatwe do pokonania przez języki gry w golfa i rodzinę APL. :)

Aby rozwinąć komentarz LegionMammal978 dla tych, którzy nie Mathematica:

##reprezentuje sekwencję parametrów funkcji (która jest jak lista, która automatycznie „wstawia” wszędzie tam, gdzie jest wstawiona, jeśli bardziej znasz ten termin z wybranego języka). ~To cukier syntaktyczny dla funkcji infix inwokacji, więc jeśli możemy wywołać funkcję z parametrami lista ni rozwijać wszystko, otrzymujemy:

Accumulate~Nest~##
Nest[Accumulate, ##]
Nest[Accumulate, list, n]

Który akurat jest dokładnie oczekiwanym porządkiem argumentów Nest.

Martin Ender
źródło
To interesujące, używając notacji SlotSequence
poprawkowej
9

Haskell, 26 23 bajtów

(!!).iterate(scanl1(+))

Definiuje funkcję anonimową, wywoływaną w następujący sposób:

> let f = (!!).iterate(scanl1(+)) in f [-3,4,7,-1,15] 3
[-3,-5,1,14,49]

Dzięki @nimi za zapisanie 3 bajtów.

Wyjaśnienie

(!!).                    -- Index by second argument from
     iterate(         )  -- the infinite list obtained by iterating
             scanl1(+)   -- the partial sums function (left scan by +) to first argument
Zgarb
źródło
Bardzo dobrze! I dziękuję za wyjaśnienie!
Jake,
2
Go pointfree, można nawet pominąć nazwę dla funkcji: (!!).iterate(scanl1(+)).
nimi
@nimi Dzięki! Jakoś pomyślałem, że kompozycja nie zadziała tutaj na moją korzyść ...
Zgarb
9

APL, 9 8 bajtów

{+\⍣⍺⊢⍵}

Definiuje to funkcję dynamiczną, która przyjmuje iteracje i listę jako argumenty lewy i prawy.

Dzięki @NBZ za grę w golfa na 1 bajcie!

Wypróbuj online na TryAPL .

Jak to działa

  • ⍺i ⍵są lewym i prawym argumentem funkcji.

  • +\ jest sumą pomniejszoną o sumę.

  • ⍣⍺powtarza poprzednie ⍺czasy operatora .

  • ⊢⍵stosuje funkcję tożsamości do ⍵.

    Jest to krótszy sposób parsowania kodu (+\⍣⍺)⍵zamiast +\⍣(⍺⍵).

W połączeniu stosujemy +\się łącznie ⍺do⍵

Dennis
źródło
@AlexA .: Czy nie byłoby +\⍣⎕⊢⎕to do przyjęcia? ( ⎕jest jak Python input()).
marinus
1
@marinus Czy to faktycznie drukuje poza REPL? Jedyni tłumacze na pulpicie, do których mam przypisane, będą ⎕później wymagali przypisania .
Dennis,
5

Matlab, 41 bajtów

function f(l,n);for i=1:n;l=cumsum(l);end

Całkiem proste. Nadal uważam, że to dość denerwujące, że nie ma wbudowanej funkcji tworzenia anonimowych funkcji lub zakotwiczania się w rekurencjach.

Nie golfowany:

function f(l,n);
for i=1:n;
    l=cumsum(l);
end
wada
źródło
5

JavaScript (ES6) 38

Zaskakująco mały przy użyciu rekurencyjnie .map

f=(l,n,t=0)=>n?f(l.map(x=>t+=x),n-1):l

function test()
{
  var n, v, i = I.value
  v = i.match(/\-?\d+/g).map(x=>+x)
  n = v.pop()
  console.log(v,n)
  O.innerHTML = I.value + ' -> ' + f(v,n) + '\n' + O.innerHTML;
}

test()
<input id=I value='[-3, 4, 7, -1, 15], 3'><button onclick="test()">-></button>
<pre id=O></pre>
Rozwiń fragment kodu

edc65
źródło
5

K, 7 3 bajty

{y+\/x}

Bardzo podobny do rozwiązania J. +\precyzyjnie wykonuje sumę częściową, a gdy /jest wyposażony w czasownik monadyczny i argument liczby całkowitej w lewo, iteruje określoną liczbę razy, jak pętla „for”. Reszta po prostu starannie ją pakuje, aby dopasować ją do kolejności argumentów.

  {y+\/x}[-3 4 7 -1 15;1]
-3 1 8 7 22
  {y+\/x}[-3 4 7 -1 15;3]
-3 -5 1 14 49

Testowane w Kona i OK .

Edytować:

Jeśli wolno mi odwrócić argumenty, jak ustalono @ kirbyfan64sos, mogę całkowicie zrezygnować z zawijania funkcji:

+\/

Wywoływano jak:

+\/[3;-3 4 7 -1 15]

Działa to poprawnie zarówno w wersji k2.8, jak i k5. Nie działa w ok, ponieważ ten interpreter nie obsługuje jeszcze przysłówków curry (inaczej „rzutowanych”) i wydaje się, że nie działa poprawnie w Kona z mniej oczywistych powodów.

edytuj : Od kilku dni +\/formuła działa również w ok.

JohnE
źródło
1
Argumenty można odwrócić , więc myślę, że możesz ogolić kilka bajtów.
kirbyfan64sos
3 +\/ -3 4 7 -1 15działa dobrze w Kona, ale nie można przypisać jej do funkcji. Dziwne ...
Dennis
Tak, Kona najwyraźniej nie traktuje 3+\/-3 4 7 -1 15tego samego jako +\/[3;-3 4 7 -1 15]- sprawia, że ​​zastanawiam się, czy potraktują to pierwsze jako specjalny przypadek składniowy.
JohnE
4

Pyth, 9 bajtów

usM._GvwQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie

usM._GvwQ  implicit: Q = input list
      vw   input number
u       Q  repeat the following instruction ^ times to G = Q
   ._G        sequence of prefixes of G
 sM           sum them up
Jakube
źródło
4

Julia, 29 bajtów

f(x,y)=y>0?f(cumsum(x),y-1):x

To naprawdę nie wymaga wielu wyjaśnień. Jest to funkcja rekurencyjna, jeśli y==0po prostu wypisuje x. W przeciwnym razie zmniejsz y, wykonaj sumę i powtórz. Prawdopodobnie nie jest to najbardziej możliwe rozwiązanie dla Julii, wciąż nad tym pracuję.

Glen O
źródło
4

Labirynt , 73 bajty

;?
,"
;
#
#;}=
;  #
"#;(
_  ;={()"
#;; ( { "
  ; { !\(@
+=( =
" " "
":{:"

Minęło trochę czasu, odkąd odpowiedziałem na coś w Labiryncie, i wydawało się to wykonalne. :)

Format wejściowy to płaska lista z liczbą iteracji najpierw (a następnie listą do zastosowania sum częściowych). Ograniczniki nie mają znaczenia, o ile po ostatniej liczbie całkowitej nie ma znaku, więc możesz użyć czegoś czytelnego:

3 | -3, 4, 7, -1, 15

Dane wyjściowe są oddzielone znakiem nowej linii:

-3
-5
1
14
49
Martin Ender
źródło
4

R, 75 bajtów

Jest długi, ale wymaga innego obliczenia ... bezpośrednie obliczenie żądanej sekwencji zamiast łącznych sum:

function(x,n)sapply(1:length(x),function(i)sum(x[1:i]*choose(i:1+n-2,n-1)))

Zwracając uwagę, że współczynniki wyrażeń xi dla sumy ^ n (x) są przekątnymi trójkąta Pascala. to znaczy

cumsum^3(x) = choose(2,2) * x1, choose(3,2) * x1 + choose(2,2) *x2, choose(4,2) * x1 + choose(3,2) * x2 + choose(2,2) * x3, ....

edycja: aby utworzyć funkcję

njnnja
źródło
4

Python 2, 67

Wykorzystuje to to samo podsumowanie co Anthony Roitman i taką samą rekurencję jak Morgan Thrapp .

f=lambda l,n:f([sum(l[:i+1])for i in range(len(l))],n-1)if n else l

Opracowałem to rozwiązanie, zanim zobaczyłem ich, a potem wydawało się, że łatwiej jest opublikować je jako odpowiedź niż komentarz do jednego lub obu z nich.

Mathmandan
źródło
4

Python, 113 93 89 76 bajtów

def f(l,n):
 for i in[0]*n:l=[sum(l[:j+1])for j in range(len(l))];
 print(l)

Działa w obu przypadkach testowych. Dzięki Status, Morgan Thrapp i Ruth Franklin za pomoc w grze w golfa odpowiednio do 93, 89 i 76 bajtów.

Anthony Roitman
źródło
1
Możesz wyciąć wiele bajtów, zmieniając drugą pętlę na listę. Oznacza to, że k=[sum(l[:j+1])for j in range(len(l))]. Następnie za pomocą ;k=lhalsu na końcu możesz przepchnąć to wszystko do jednej linii za pomocą for ipętli.
Status
1
Możesz przenieść ten k=[sum(l[:j+1])for j in range(len(l))];l=kwiersz do pętli for, aby zapisać 2 bajty i usunąć odstęp między argumentami f, aby zapisać kolejny bajt.
Morgan Thrapp,
Jak nie użyć wartości i, można zastąpić for i in range(n)z for i in[0]*n(ponieważ wszystko zależy Ci na to nie długość elementy listy). I myślę, że możesz to zrobić bez użycia listy pomocniczej k, po prostu modyfikując argument l.
Ruth Franklin
4

Gol> <> 0.3.10 , 22 bajty

SI
C>rFlMF:}+
NRl<C}<;

Pierwszą liczbą całkowitą jest numer iteracji, a resztę tworzą listę. Ostateczna lista jest wyprowadzana rozdzielona znakiem nowej linii.

Język jest wciąż dość młody i niestabilny, ale ponieważ jestem dość nastawiony na tych operatorów, pomyślałem, że będzie dobrze.

Wyjaśnienie

SI            Read integer, moving down on EOF (first line runs as loop)
r             Reverse stack, putting iteration number on top

[outer loop]
F             Do #(iterations) times

[inner loop]
lMF           Do #(length of stack - 1) times
:             Duplicate top of stack
}             Rotate stack rightward (top goes to bottom)
+             Add the top two elements of the stack
C             Continue inner loop, moving down from F when loop is over

}             Rotate once more
C             Continue outer loop, moving down from F when loop is over

lRN           Print stack as (num + newline)
;             Halt

Aby zobaczyć, dlaczego to działa, spróbujmy małego przykładu [5 2 1]:

[5 2 1] -- : --> [5 2 1 1] -- } -->  [1 5 2 1]  -- + --> [1 5 3]
[1 5 3] -- : --> [1 5 3 3] -- } -->  [3 1 5 3]  -- + --> [3 1 8]

-- } --> [8 3 1]
Sp3000
źródło
3

Python, 52 bajty

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

Funkcja rekurencyjna, która powtarza oba na liście l i liczbie iteracji n. Rozbijmy to.

Najpierw rozważmy funkcję rekurencyjną, gktóra tylko raz powtórzyła sumę częściową.

g=lambda l:l and g(l[:-1])+[sum(l)]

W przypadku pustej listy lzwraca ona lsamą pustą listę. W przeciwnym razie ostatni wpis częściowych sum ljest sumą całkowitą l, która jest dołączana do wyniku rekurencyjnego dla wszystkich elementów oprócz ostatniego l.

Spójrzmy teraz spójrzmy prawdzie w funkcję f, która ma zastosowanie gdon iteracji.

f=lambda l,n:n and f(g(l),n-1)or l

Kiedy njest 0, zwraca listę lniezmienioną, a w przeciwnym razie ma zastosowanieg raz, a następnie wywołuje frekurencyjnie, pozostawiając jeszcze jedną iterację.

Teraz spójrzmy jeszcze raz na rzeczywisty kod, który łączy dwie rekurencje w jedną funkcję. Chodzi o to, aby traktować g(l)jako szczególny przypadek f(l,1).

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

Wzięliśmy f(g(l),n-1)z poprzedniej definicji, rozszerzył g(l)się g(l[:-1])+[sum(l)], a następnie otrzymuje g(_)zf(_,1) aby ograniczyć rekurencyjne wywołania do f.

W przypadku podstawowym chcemy powrócić lzawsze n==0lub l==[]. Łączymy je, zauważając, że jedno z nich powoduje, że n*ljest pustą listą, którą jest Falsy. Tak więc powtarzamy za każdym razem, gdy n*lnie jest pusty, i wracamy w lprzeciwnym razie.

Mimo że istnieją dwa rekurencyjne wezwania do f, nie powoduje to wykładniczego powiększenia rekurencyjnej definicji liczb Fibonacciego, ale pozostaje kwadratowe.

xnor
źródło
3

C ++ (61 + 17 = 78 bajtów)

#include<numeric>
void f(int*a,int*e,int n){for(;n--;)std::partial_sum(a,e,a);}

Przypadek testowy:

#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    f(a, std::end(a), 3);
    for (auto i : a)
        std::cout << i << " ";
}

Ta specyfikacja ma niewielką swobodę: wykorzystuje tablicę w stylu C, przekazując wskaźniki na początek i na końcu tablicy. Wewnętrznie, jak widać, jest to tylko wyjątkowo cienkie opakowanie std::partial_sumw standardowej bibliotece. Zamiast faktycznie zwracać wynikową wartość, modyfikuje tylko przekazaną tablicę.

Jeśli nie przeszkadza nam przesuwanie definicji rzeczy do granic możliwości (i prawdopodobnie nieco dalej), możemy zdefiniować „funkcję” w wyrażeniu lambda:

#include<numeric>
#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    int *e = std::end(a);
    int n=3;

    auto f=[&]{for(;n--;)std::partial_sum(a,e,a);};

    f();
    for (auto i : a)
        std::cout << i << " ";
}

Zmniejsza to definicję funkcji (obiektu podobnego do obiektu) do tego fragmentu:

[&]{for(;n--;)std::partial_sum(a,e,a);};

... dla 40 bajtów (+17 dla #include).

Jerry Coffin
źródło
Wau, nie spodziewałem się, że STL będzie miał algę do liczenia częściowych sum.
Zereges
1
@Zereges: Nikt nie spodziewa się hiszpańskiego inkwizytora ... och, czekaj, robimy C ++, nie Python. Przepraszam.
Jerry Coffin
2

Haskell, 52 47 bajtów

Pierwsza w historii „próba” golfa kodowego, a ja jestem początkującym Haskellem, więc komentarze są mile widziane! W pytaniu nie było jasne, jaki jest konieczny format wywołania funkcji ani czy został on pobrany przez program do argumentu, więc użyłem wykrzyknika jako identyfikatora funkcji, aby zaoszczędzić kilka spacji.

0!a=a
i!a=(i-1)![sum$take j a|j<-[1..length a]]

Zastosowanie (GHCi):

$ ghci partialsums.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( partialsums.hs, interpreted )
Ok, modules loaded: Main.
*Main> 1![-3, 4 ,7 ,-1 ,15]
[-3,1,8,7,22]
*Main> 3![-3, 4 ,7 ,-1 ,15]
[-3,-5,1,14,49]
Jake
źródło
Witamy w Code Golf! Zazwyczaj dopasowanie wzoru jest krótsze niż użycie osłon, takich jak 0!a=a i!a=....
xnor
Dzięki @xnor - poprzednio użyłem „xs” podczas budowania kodu początkowego i musiałem go pominąć, kiedy zmodyfikowałem kod w poście. Edytowany.
Jake,
Ponieważ sum(take j a)możesz uniknąć parens, wykonując tę ​​czynność sum$take j a, stosując wysoki priorytet $.
xnor
Dziękuję za pomoc! Z jakiegoś powodu miałem wrażenie, że $miałoby ono pierwszeństwo przed składnią (i spróbowałem ocenić resztę wiersza w obecnej formie). Oczywiście nie miałoby to nawet sensu.
Jake,
2

R, 41 bajtów

function(x,n){for(i in 1:n)x=cumsum(x);x}
flodel
źródło
2

C #, 52 + 85 = 148 137 bajtów

using E=System.Collections.Generic.IEnumerable<int>;

i

E I(E s,int i){int t=0;return i<1?s:I(System.Linq.Enumerable.Select(s,v=>t+=v),i-1);}

Wykorzystuje niekonwencjonalne praktyki ( v=>t+=v), ale jest to PPCG. Zwróć również uwagę na ograniczenie głębokości stosu.

LegionMammal978
źródło
2

Python 3, 73

Prawdopodobnie można go nieco pograć w golfa.

def f(n,i):
 p=0;c=[]
 for m in n:p+=m;c+=[p]
 f(c,i-1)if i else print(n)

Ta wersja używa numpy, co przypomina trochę oszustwo, ale oto:

Python 3 (z numpy), 72

from numpy import*
def f(n,i):
 if i:c=cumsum(n);f(c,i-1)
 else:print(n)
Morgan Thrapp
źródło
2

C ++ 14, 102 103 94 + 17 (dołącz) = 111 bajtów

#include<vector>
auto f(std::vector<int>a,int n){for(;n--;)for(int i=0;i<a.size()-1;++i)a[i+1]+=a[i];return a;}

Bez golfa, z walizką testową

#include <vector>
#include <iostream>

auto f(std::vector<int> a, int n)
{
    for (; n--;)
        for (int i = 0; i < a.size() - 1; ++i)
            a[i + 1] += a[i];
    return a;
}


int main()
{
    auto t = f({-3, 4, 7, -1, 15}, 3);
    for (int i : t)
        std::cout << i << " ";
}

Opiera się na kolejności oceny. Nie jestem pewien, czy jest to UB, czy nie, ale działa To zależy od kompilatora, więc go zmieniłem.

Zereges
źródło
Zamiast jzliczać od 0 do n, odliczaj ndo 0. Daje 97 bajtów według mojej liczby.
Jerry Coffin
@JerryCoffin Dzięki ..
Zereges
1

Oktawa, 24 bajty

@(l,n)l*triu(0*l'*l+1)^n
alephalpha
źródło
1

Burleska, 10 bajtów

{q++pa}jE!

ogólnie nie jest bardzo wydajny, ale działa.

blsq ) {-3 4 7 -1 15} 1 {q++pa}jE!
{-3 1 8 7 22}
blsq ) {-3 4 7 -1 15} 3 {q++pa}jE!
{-3 -5 1 14 49}
mroman
źródło
1

C ++ 14, 67 bajtów

Jako nienazwana lambda modyfikująca dane wejściowe, wymagająca cpodobnie jak kontener o swobodnym dostępie vector<int>.

[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}
Karl Napf
źródło
1

05AB1E , 4 bajty (prawdopodobnie niekonkurencyjne)

F.pO

F    # Implicitly take first input and loop n times.
 .p  # Generate prefixes of input.
   O # Sum all prefixes (implicitly vectorized).

Wypróbuj online!

Urna Magicznej Ośmiornicy
źródło
1

Galaretka , 3 bajty

SƤ¡

Wypróbuj online!

To jest moja metoda ( pana Xcodera ).

Galaretka , 3 bajty

+\¡

Wypróbuj online!

To rozwiązanie Cairna Coheringaahinga .

Metoda nr 1

SƤ¡ - Pełny program, dynamiczny.

  ¡- Stosuj wielokrotnie, N razy.
 Ƥ - Zamapuj poprzedni link nad prefiksami listy.
S - Suma.
     - Wynik niejawny

Metoda nr 2

+ \ ¡- Pełny program, dynamiczny.

  ¡- Stosuj wielokrotnie, N razy.
 \ - Skumulowane zmniejszenie o:
+ - Dodawanie.
Mr. Xcoder
źródło
0

Axiom 213 47 bajtów

m(a,b)==(for i in 1..b repeat a:=scan(+,a,0);a)

Ungolf i jakiś przykład

 (3) -> [m([-3,4,7,-1,15],1), m([-3,4,7,-1,15],3)]
    Compiling function l with type List Integer -> List Integer
    Compiling function m with type (List Integer,Integer) -> List
       Integer

    (3)  [[- 3,1,8,7,22],[- 3,- 5,1,14,49]]
                                                       Type: List List Integer
RosLuP
źródło