Sumas parciales iteradas

23

Las sumas parciales de una lista de enteros [a 1 , a 2 , a 3 , ..., a n ] son

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

Luego podemos tomar la lista de sumas parciales [s 1 , s 2 , s 3 , ..., s n ] y calcular sus sumas parciales nuevamente para producir una nueva lista, y así sucesivamente.

Relacionado: Diferencias hacia adelante iteradas

Entrada:

  • Una lista de enteros no vacía
  • Un número positivo de iteraciones,

Salida: Imprima o devuelva la lista de enteros que resulta de tomar las sumas parciales muchas veces.

Pocos bytes ganan. Los empotrados están bien incluso si resuelven el problema por completo.

Casos de prueba:

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

Tabla de clasificación:

Mostrar fragmento de código

code-golf number arithmetic sequence array-manipulation xnor
fuente
¿Es necesario que los argumentos estén en el mismo orden o el número de iteraciones puede aparecer antes de la lista de números?
kirbyfan64sos
@ kirbyfan64sos Cualquiera de los dos pedidos.
xnor

Respuestas:

14

J, 5 bytes

+/\^:

Pruébelo en línea en J.js .

Cómo funciona

  • /\ es un adverbio (función que toma un argumento izquierdo) que se reduce acumulativamente por su argumento.

  • Así +/\es el verbo de suma acumulativa .

  • ^:es la conjunción de poder ; (f ^: n) yaplica fun total de nveces a y.

  • El tren verbo-conjunción +/\^:forma un adverbio que se repite +/\tantas veces como se especifica en su argumento (izquierdo).

    x (+/\^:) yse analiza como (x (+/\^:)) y, lo que equivale a ejecutar (+/\^:x) y.

Gracias a @Zgarb por su ayuda con la explicación.

Dennis
fuente
13

Mathematica, 19 bytes

Bueno, si los complementos están bien ...

Accumulate~Nest~##&

Define una función con la misma firma que los ejemplos en el desafío. Sin Accumulateembargo, estoy bastante seguro, gracias al largo nombre de que esto será fácilmente superado por los idiomas de golf y la familia APL. :)

Para elaborar el comentario de LegionMammal978 para aquellos que no tienen Mathematica:

##representa una secuencia de los parámetros de la función (que es como una lista que "salpica" automáticamente donde sea que se inserte, si está más familiarizado con ese término del idioma de su elección). El ~son azúcar sintáctica para invocación de la función infija, por lo que si llamamos a la función con parámetros listy ny ampliar todo, obtenemos:

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

Que resulta ser exactamente el orden de argumento esperado por Nest.

Martin Ender
fuente
Eso es interesante, usando notación infija para 3 argumentos usando SlotSequence...
LegionMammal978
9

Haskell, 26 23 bytes

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

Esto define una función anónima, invocada de la siguiente manera:

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

Gracias a @nimi por guardar 3 bytes.

Explicación

(!!).                    -- Index by second argument from
     iterate(         )  -- the infinite list obtained by iterating
             scanl1(+)   -- the partial sums function (left scan by +) to first argument
Zgarb
fuente
¡Muy agradable! Y gracias por la explicación!
Jake
2
Ir pointfree, después, se puede omitir el nombre de la función: (!!).iterate(scanl1(+)).
nimi
@nimi ¡Gracias! De alguna manera razoné que la composición no funcionaría para mi ventaja aquí ...
Zgarb
9

APL, 9 8 bytes

{+\⍣⍺⊢⍵}

Esto define una función diádica que acepta las iteraciones y la lista como argumentos izquierdo y derecho.

¡Gracias a @NBZ por jugar golf en 1 byte!

Pruébelo en línea en TryAPL .

Cómo funciona

  • ⍺y ⍵son los argumentos izquierdo y derecho de la función.

  • +\ es acumulativo reducir por suma.

  • ⍣⍺repite los ⍺tiempos de operador anteriores .

  • ⊢⍵aplica la función de identidad a ⍵.

    Esta es una forma más corta de analizar el código en (+\⍣⍺)⍵lugar de +\⍣(⍺⍵).

En conjunto, aplicamos +\un total de ⍺veces a⍵

Dennis
fuente
@AlexA .: ¿Entonces no +\⍣⎕⊢⎕sería aceptable? ( ⎕Es como Python input()).
Marinus
1
@marinus ¿Eso realmente se imprime fuera de un REPL? Los únicos intérpretes de escritorio que tengo requerirían asignarlos ⎕después.
Dennis
5

Matlab, 41 bytes

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

Bastante sencillo. Todavía creo que es bastante molesto no tener una forma integrada de hacer funciones anónimas definidas por partes, o anclas en las recursiones.

Sin golf:

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

JavaScript (ES6) 38

Sorprendentemente pequeño usando .map recursivamente

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>
Expandir fragmento

edc65
fuente
5

K, 7 3 bytes

{y+\/x}

Muy similar a la solución J. +\realiza con precisión una suma parcial, y cuando /se le proporciona un verbo monádico y un argumento entero a la izquierda, itera un número específico de veces, como un bucle "for". El resto es simplemente envolverlo perfectamente para adaptarse al orden de los argumentos.

  {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

Probado en Kona y OK .

Editar:

Si se me permite revertir los argumentos, como determinó @ kirbyfan64sos, puedo prescindir completamente de la función:

+\/

Invocado como:

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

Esto funciona correctamente tanto en k2.8 como en k5. No funciona en OK ya que ese intérprete aún no admite adverbios curry (también conocido como "proyectado"), y no parece funcionar correctamente en Kona por razones menos claras.

editar : Desde hace unos días, la +\/formulación también funciona en OK.

JohnE
fuente
1
Los argumentos se pueden revertir , por lo que creo que puede reducir algunos bytes.
kirbyfan64sos
3 +\/ -3 4 7 -1 15funciona bien en Kona, pero no puede asignarlo a una función. Extraño ...
Dennis
Sí, Kona claramente no está tratando 3+\/-3 4 7 -1 15lo mismo que +\/[3;-3 4 7 -1 15]... me hace preguntarme si manejan el primero como un caso sintáctico especial.
JohnE
4

Pyth, 9 bytes

usM._GvwQ

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación

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
fuente
4

Julia, 29 bytes

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

Esto realmente no necesita mucha explicación. Es una función recursiva, si y==0solo emite x. De lo contrario, disminuya y, realice un cumsum y recurse. Probablemente no sea la solución de Julia más golfizada posible, todavía estoy trabajando en ello.

Glen O
fuente
4

Laberinto , 73 bytes

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

Ha pasado un tiempo desde que respondí algo en Labyrinth, y esto parecía factible. :)

El formato de entrada es una lista plana con el número de iteraciones primero (y luego la lista para aplicar las sumas parciales). Los delimitadores no importan todos, siempre que no haya caracteres después del último entero, por lo que puede usar algo legible como:

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

La salida está separada por nueva línea:

-3
-5
1
14
49
Martin Ender
fuente
4

R, 75 bytes

Es largo pero una toma diferente ... calcular la secuencia deseada directamente en lugar de sumas acumulativas:

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

Observando que los coeficientes de los términos de xi para cumsum ^ n (x) son diagonales del triángulo de Pascal. es decir

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, ....

editar: para hacer una función

njnnja
fuente
4

Pitón 2, 67

Utiliza el mismo resumen que Anthony Roitman y la misma recursión que Morgan Thrapp .

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

Desarrollé esta solución antes de ver la suya, y luego me pareció más fácil publicarla como una respuesta en lugar de un comentario para uno o ambos.

Mathmandan
fuente
4

Python, 113 93 89 76 bytes

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

Funciona para ambos casos de prueba. Gracias a Status, Morgan Thrapp y Ruth Franklin por ayudarme a jugar golf en el programa hasta 93, 89 y 76 bytes respectivamente.

Anthony Roitman
fuente
1
Puede recortar una cantidad de bytes cambiando el segundo bucle en una lista de comprensión. Es decir, k=[sum(l[:j+1])for j in range(len(l))]. Luego, con ;k=lel extremo clavado al final, puede empujar todo esto en una línea con el for ibucle.
Estado del
1
Puede moverlo k=[sum(l[:j+1])for j in range(len(l))];l=ka la misma línea que el bucle for para guardar 2 bytes y eliminar el espacio entre los argumentos de f para guardar otro byte.
Morgan Thrapp
Como no usa el valor de i, puede reemplazar for i in range(n)con for i in[0]*n(porque lo único que le importa es la longitud, no los elementos de la lista). Y creo que puedes hacerlo sin usar la lista auxiliar k, solo modificando el argumento l.
Ruth Franklin
4

Gol> <> 0.3.10 , 22 bytes

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

Se considera que el primer entero es el número de iteración y el resto forma la lista. La lista final se muestra separada por una nueva línea.

El lenguaje aún es bastante joven e inestable, pero como estoy bastante concentrado en estos operadores, pensé que estaría bien.

Explicación

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

Para ver por qué esto funciona, intentemos con un pequeño ejemplo [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
fuente
3

Python, 52 bytes

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

Una función recursiva que se repite tanto en la lista lcomo en el número de iteraciones n. Vamos a desglosarlo.

Primero, consideremos una función recursiva gque itera la suma parcial solo una vez.

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

Para una lista vacía l, esto se devuelve a lsí mismo, la lista vacía. De lo contrario, la última entrada de las sumas parciales de les la suma total de l, que se agrega al resultado recursivo para todos menos el último elemento de l.

Ahora, veamos una función fque se aplica ga las niteraciones.

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

Cuando nes así 0, esto devuelve la lista lsin cambios, y de lo contrario, se aplica guna vez, luego llama frecursivamente con una iteración menos restante.

Ahora, veamos nuevamente el código real, que combina las dos recursiones en una sola función. La idea es tratar g(l)como el caso especial f(l,1).

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

Llevamos a f(g(l),n-1)partir de la definición anterior, se expandió g(l)en g(l[:-1])+[sum(l)], y luego reemplazado g(_)con f(_,1)que limita las llamadas recursivas a f.

Para el caso base, queremos volver lcuando n==0o l==[]. Combinamos esto notando que cualquiera de los dos n*les la lista vacía, que es Falsy. Por lo tanto, recurrimos cuando n*lno está vacío y regresamos de lo lcontrario.

Aunque hay dos llamadas recursivas a f, esto no causa una explosión exponencial de la definición recursiva de los números de Fibonacci, pero sigue siendo cuadrática.

xnor
fuente
3

C ++ (61 + 17 = 78 bytes)

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

Caso de prueba:

#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 << " ";
}

Esto toma un poco de libertad con la especificación: utiliza una matriz de estilo C, pasando punteros al principio y al final de la matriz. Internamente, como puede ver, es solo un envoltorio extremadamente delgado alrededor std::partial_sumde la biblioteca estándar. En lugar de devolver el valor resultante, simplemente modifica la matriz que se pasa.

Si no nos importa llevar las definiciones de las cosas al límite (y, posiblemente, un poco más allá) podemos definir una "función" en una expresión 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 << " ";
}

Esto reduce la definición de la función (objeto similar) a esta pieza:

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

... para 40 bytes (+17 para el #include).

Jerry Coffin
fuente
Wau, no esperaba que STL tuviera alg para contar sumas parciales.
Zereges
1
@Zereges: Nadie espera la Inquisición española ... oh, espera, estamos haciendo C ++, no Python. Mis disculpas.
Jerry Coffin
2

Haskell, 52 47 bytes

Primer código de 'intento' de golf, y soy un principiante de Haskell, ¡así que los comentarios son bienvenidos! No estaba claro en la pregunta sobre el formato necesario de la llamada a la función, o si fue tomada por un argumento al programa, por lo que utilicé el signo de exclamación como el identificador de la función para guardar un par de espacios.

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

Uso (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
fuente
Bienvenido a code golf! Por lo general, es más corto combinar patrones que usar guardias, como 0!a=a i!a=....
xnor
Gracias @xnor: anteriormente había usado 'xs' al construir el código inicial y debí haberlo perdido cuando modifiqué el código en la publicación. Editado
Jake
Para sum(take j a), puede evitar los pares haciendo sum$take j a, usando la alta prioridad de $.
xnor
¡Gracias por tu ayuda! Estaba, por alguna razón, bajo la impresión de que $tendría prioridad sobre la sintaxis (y tratar de evaluar el resto de la línea tal como está). Por supuesto, eso ni siquiera tendría sentido.
Jake
2

R, 41 bytes

function(x,n){for(i in 1:n)x=cumsum(x);x}
flodel
fuente
2

C #, 52 + 85 = 148137 bytes

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

y

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

Utiliza prácticas poco ortodoxas ( v=>t+=v), pero esto es PPCG. También tenga en cuenta la restricción de profundidad de pila.

LegionMammal978
fuente
2

Pitón 3, 73

Probablemente podría jugar golf un poco más lejos.

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

Esta versión usa numpy, que se siente un poco como hacer trampa, pero aquí está:

Python 3 (con numpy), 72

from numpy import*
def f(n,i):
 if i:c=cumsum(n);f(c,i-1)
 else:print(n)
Morgan Thrapp
fuente
2

C ++ 14, 102 103 94 + 17 (incluir) = 111 bytes

#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;}

Sin golf, con caso de prueba

#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 << " ";
}

Se basa en el orden de evaluación. No estoy seguro si es UB o no, pero funciona. Es dependiente del compilador, así que lo cambié.

Zereges
fuente
En lugar de contar jde 0 a n, cuenta nregresiva hasta 0. Da 97 bytes por mi cuenta.
Jerry Coffin
@JerryCoffin Gracias ..
Zereges
1

Octava, 24 bytes

@(l,n)l*triu(0*l'*l+1)^n
alephalpha
fuente
1

Burlesque, 10 bytes

{q++pa}jE!

No es muy eficiente en general, pero funciona.

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
fuente
1

C ++ 14, 67 bytes

Como lambda sin nombre modificando su entrada, requiriendo ccomo un contenedor de acceso aleatorio como vector<int>.

[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}
Karl Napf
fuente
1

05AB1E , 4 bytes (probablemente no compite)

F.pO

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

Pruébalo en línea!

Urna de pulpo mágico
fuente
1

Jalea , 3 bytes

SƤ¡

Pruébalo en línea!

Este es mi método (del Sr. Xcoder ).

Jalea , 3 bytes

+\¡

Pruébalo en línea!

Esta es la solución de caird coinheringaahing .

Método 1

SƤ¡ - Programa completo, diádico.

  ¡- Aplicar repetidamente, N veces.
 Ƥ - Asigna el enlace anterior sobre los prefijos de la lista.
S - Suma.
     - Salida implícita

Método 2

+ \ ¡- Programa completo, diádico.

  ¡- Aplicar repetidamente, N veces.
 \ - Reducción acumulativa por:
+ - Suma.
Sr. Xcoder
fuente
0

Axiom 213 47 bytes

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

ungolf y algún ejemplo

 (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
fuente