Considere una variedad Ade longitud n. La matriz contiene solo enteros positivos. Por ejemplo A = (1,1,2,2). Definamos f(A)como el conjunto de sumas de todos los subconjuntos contiguos no vacíos de A. En este caso f(A) = {1,2,3,4,5,6}. Los pasos para producir f(A) son los siguientes:

Las submatrices de Ason (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Sus sumas respectivas son 1,1,2,2,2,3,4,4,5,6. El conjunto que obtienes de esta lista es por lo tanto {1,2,3,4,5,6}.

Tarea

Dado un conjunto de sumas Sdadas en orden ordenado que contiene solo enteros positivos y una longitud de matriz n, su tarea es generar al menos una matriz de Xtal manera f(X) = S.

Por ejemplo, si S = {1,2,3,5,6}y n = 3luego es una salida válida X = (1,2,3).

Si no existe dicha matriz, Xsu código debería generar un valor constante.

Ejemplos

Entrada: n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13)salida posible:X = (3, 5, 1, 4)

Entrada: n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)salida posible:X = (5, 3, 2, 2, 5, 5)

Entrada: n=6, S = (2, 4, 6, 8, 10, 12, 16)salida posible:X = (4, 2, 2, 2, 2, 4)

Entrada: n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14)salida posible:X = (4, 2, 1, 1, 2, 4)

Entrada: 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), posible salida: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5).

Entrada: 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), posible salida: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3).

Formato de entrada y salida.

Su código puede recibir entrada y salida en cualquier formato de lectura humana que le resulte conveniente. Sin embargo, muestre el resultado de probarlo en los ejemplos de la pregunta.

Tiempo de ejecución

Debe poder ejecutar el código hasta su finalización para todos los ejemplos en la pregunta. En principio, debería ser correcto n, 15pero no es necesario demostrar que sería lo suficientemente rápido para todas las entradas.

Casco , 20 bytes

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

Pruébalo en línea!

Devuelve una solución o una lista vacía si no existe. El último caso de prueba ( n=15) termina en 3.8 segundos en TIO.

Explicación

El programa tiene dos partes. En la primera parte ( ¡y a la derecha de la misma), construimos una lista infinita cuyo kelemento th es una lista que contiene todas las klistas de longitud cuyas sumas de corte están incluidas S. Hacemos esto inductivamente, comenzando desde los segmentos de 1 elemento Sy, en cada paso, anteponiendo cada elemento de Sa cada lista, y manteniendo aquellos cuyas sumas de prefijo están en S. En la segunda parte ( !ya la izquierda de la misma), tomamos el nelemento th de la lista, que contiene nlistas de longitud . De estos, seleccionamos el primero cuyas sumas de corte contienen cada elemento de S.

En el código, primero reemplacemos oy ȯ(que componen dos y tres funciones en una) por paréntesis para mayor claridad.

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

Hay algunas partes que necesitan más explicación. En este programa, los superíndices se ⁰¹refieren al primer argumento S. Sin embargo, si αes una función, α¹significa "aplicar αa S", mientras que ⁰αsignifica "conectar Sal segundo argumento de α". La función ¦verifica si su primer argumento contiene todos los elementos del segundo (contando multiplicidades), por lo que Sdebería ser su segundo argumento.

En la primera parte, la función que ¡utiliza se puede interpretar como S(f~Λ€∫)(×:)¹. El combinador se Scomporta como Sαβγ -> (αγ)(βγ), lo que significa que podemos simplificarlo (f~Λ€∫¹)(×:¹). La segunda parte, ×:¹es "mezclar con Santeponer", y su resultado se pasa a la primera parte. La primera parte f~Λ€∫¹, funciona así. La función ffiltra una lista por una condición, que en este caso es ~Λ€∫¹. Recibe una lista de listas L, por lo que tenemos ~Λ€∫¹L. El combinador se ~comporta como ~αβγδε -> α(βδ)(γε): el primer argumento se pasa a β, el segundo a γ, y los resultados se combinan con α. Esto significa que tenemos Λ(€¹)(∫L). La última parte ∫Lson solo las sumas acumuladas de L,€¹es una función que registra la membresía Sy Λtoma una condición (aquí €¹) y una lista (aquí ∫L), y verifica que todos los elementos la satisfagan. En pocas palabras, filtramos los resultados de la mezcla según si todas las sumas acumulativas están incluidas S.

Ruby , 135 bytes

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

Pruébalo en línea!

Use una búsqueda de amplitud. n = 10 funciona en TIO, n = 15 lleva más de un minuto, pero funciona en mi máquina.

Rubí , 147 bytes

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

Pruébalo en línea!

Versión optimizada, funciona en TIO para n = 15 (~ 20 segundos)

En realidad, este es el comienzo de un enfoque de fuerza no bruta. Espero que alguien trabaje en ello y encuentre una solución completa.

Primeras ideas:

• La suma de la matriz de salida es el último elemento (máximo) de la matriz de entrada.
• La suma de la matriz de salida menos el primer (o el último) elemento, es el segundo último elemento de la matriz de entrada.
• Si una matriz es una solución, entonces la matriz inversa también es una solución, por lo que podemos suponer que el primer elemento es la diferencia entre los últimos 2 elementos de la matriz de entrada.
• El segundo elemento puede ser la diferencia entre el segundo y tercer o segundo y cuarto último elemento de la matriz de entrada.

Lo que nos lleva a la próxima optimización:

Ruby , 175 bytes

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

Pruébalo en línea!

~ 8.5 segundos en TIO. No está mal...

... y así sucesivamente (para ser implementado)

Haskell, 117111 bytes

¡6 bytes guardados gracias a @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

Pruébalo en línea!

fr$S$ins

Cuando nes cero (golfed n<1) la lista debe estar lista, por lo que verificamos si se han visto todos los valores. Si no, devolvemos una lista vacía para indicar que no hay soluciones, de lo contrario, devolvemos una lista singleton que contiene una lista vacía, a la que se agregarán los elementos elegidos. Este caso también podría haberse manejado con las ecuaciones adicionales

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

Si nno es cero, volvemos

[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.............^

Esta es la lista de (1) listas de donde proviene el primer elemento (2) sy el resto (5) proviene de la llamada recursiva, bajo la condición (4) de que se encuentran todas las sumas nuevas s. Las nuevas sumas se calculan en (3): tenga en cuenta que tse extrae de una lista única, un truco de golf feo para lo que en el idiomático de Haskell sería let t=y:map(y+)i. La llamada recursiva (5) obtiene como nuevo rconjunto el antiguo sin esos elementos que aparecen entre las nuevas sumas t.

La función principal &llama a la función auxiliar diciendo que todavía tenemos que ver todos los valores ( r=s) y que todavía no hay sumas ( i=[]).

Para siete bytes más, podemos restringir el cálculo para dar solo el primer resultado (si lo hay), que es mucho más rápido y maneja todos los casos de prueba en menos de 2 segundos.

Pruébalo en línea! (este es el primer resultado solo variación de la versión anterior)

Limpio , 177 bytes

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]]

Pruébalo en línea!

Toma alrededor de 40 segundos en mi máquina para el n=15caso de prueba, pero se agota en TIO.

Limpio , 297 bytes

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]]

Pruébalo en línea!

Este incluye algunas optimizaciones hechas por GB , así como algunas mías. Creo que algunos de ellos pueden hacerse más genéricos, por lo que agregaré una explicación una vez que haya terminado.

Tarda unos 10 segundos en mi máquina, 40 segundos en TIO.

Python 3 , 177 bytes

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)

Pruébalo en línea!

(se agregaron algunas líneas / espacios nuevos para evitar que los lectores tengan que desplazarse por el código)

Un puerto directo de mi respuesta Jelly (con algunas modificaciones, consulte la sección "nota" a continuación)

Resultado de ejecución local:

[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]$ 

Escuché que itertoolses detallado, pero mi mejor combinationsimplementación es aún más detallada:

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]

Nota .

• Usar división / módulo en a[p//n:p%n+1]toma aproximadamente 2 veces más, pero ahorra algunos bytes.
• Esto es un poco diferente de la respuesta Jelly: la respuesta Jelly se itera hacia atrás.
• Gracias a combinationsdevolver un iterador, esto es más amigable con la memoria.

Jalea , 35 bytes

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

Pruébalo en línea!

Ejecutar localmente: (n = 15 requiere más de 1 GB de 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

(en realidad ejecuté la versión codificada en UTF8, que toma más de 35 bytes, pero el resultado es el mismo de todos modos)

Esta solución utiliza cortocircuito para reducir el tiempo de ejecución.

$\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$

Explicación

Observamos que las sumas de todos los prefijos no vacíos están presentes en la entrada y están aumentando estrictamente. También podemos suponer que el elemento más grande y el segundo más grande es una suma de prefijo.

$n-2$$|S|-2$$\binom {|S|-2}{n-2}$$n^2$$n^3 \over 6$

No probado (pero debe tener un rendimiento idéntico)

Jalea , 32 bytes

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

Pruébalo en línea!

Versión más ineficiente (sin cortocircuito):

Jalea , 27 bytes

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

Pruébalo en línea!

Para la prueba n = 15, toma hasta 2 GB de RAM y no termina después de ~ 37 minutos.

nota : Ẇ§puede ser reemplazado con ÄÐƤẎ. Puede ser más eficiente.

APL (NARS), caracteres 758, bytes 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

La función G en G x (con la ayuda de la función H) encontraría todas las permutaciones de x. La función d en xdy busca si la matriz y se genera siguiendo la matriz de ejercicios x que devuelve un valor booleano. La función F en x F y devolvería la matriz r de longitud x, de modo que ydr es verdadero (= 1) Un poco más largo que la implementación, pero es este el que calcula todos los casos en la prueba menos tiempo ... El último caso para n = 15 se ejecuta solo 20 segundos ... tengo que decir que no encuentra muchas soluciones, devuelve solo una solución (por fin parece) en menos tiempo (prueba no explorada para diferentes entradas ...) 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