Considérez un tableau Ade longueur n. Le tableau ne contient que des entiers positifs. Par exemple A = (1,1,2,2). Définissons f(A)comme l'ensemble des sommes de tous les sous-réseaux contigus non vides de A. Dans ce cas f(A) = {1,2,3,4,5,6}. Les étapes de production f(A) sont les suivantes:

Les sous-réseaux de Asont (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Leurs sommes respectives sont 1,1,2,2,2,3,4,4,5,6. L'ensemble que vous obtenez de cette liste est donc {1,2,3,4,5,6}.

Tâche

Étant donné un ensemble de sommes Sdonnées dans un ordre trié ne contenant que des entiers positifs et une longueur de tableau n, votre tâche consiste à générer au moins un tableau Xtel que f(X) = S.

Par exemple, si S = {1,2,3,5,6}et n = 3alors une sortie valide est X = (1,2,3).

S'il n'y a pas un tel tableau, Xvotre code devrait afficher n'importe quelle valeur constante.

Exemples

Entrée n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13):, sortie possible:X = (3, 5, 1, 4)

Entrée n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22):, sortie possible:X = (5, 3, 2, 2, 5, 5)

Entrée n=6, S = (2, 4, 6, 8, 10, 12, 16):, sortie possible:X = (4, 2, 2, 2, 2, 4)

Entrée n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14):, sortie possible:X = (4, 2, 1, 1, 2, 4)

Entrée: 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), sortie possible: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5).

Entrée: 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), sortie possible: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3).

Format d'entrée et de sortie

Votre code peut prendre en entrée et donner une sortie dans n'importe quel format de lecture facilement humain que vous trouvez commode. Cependant, veuillez montrer le résultat du test sur les exemples de la question.

Durée

Vous devez être en mesure d'exécuter le code jusqu'à la fin pour tous les exemples de la question. Il devrait en principe être correct njusqu'à 15mais vous n'avez pas besoin de prouver qu'il serait assez rapide pour toutes les entrées.

Coque , 20 octets

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

Essayez-le en ligne!

Renvoie une solution ou une liste vide si elle n'existe pas. Le dernier cas de test ( n=15) se termine en 3,8 secondes sur TIO.

Explication

Le programme comprend deux parties. Dans la première partie ( ¡et à droite de celle-ci), nous construisons une liste infinie dont le kth élément est une liste contenant toutes les klistes de longueur dont les sommes de tranche sont dedans S. Nous le faisons de manière inductive, en commençant par les tranches de 1 élément de S, et à chaque étape en ajoutant chaque élément de Sà chaque liste, et en conservant ceux dont les sommes de préfixe sont dedans S. Dans la deuxième partie ( !et à gauche), nous prenons le ne élément de la liste, qui contient les nlistes de longueurs . Parmi ceux-ci, nous sélectionnons le premier dont les sommes de tranche contiennent réellement chaque élément de S.

Dans le code, remplaçons d'abord oet ȯ(qui composent deux et trois fonctions en une) par des parenthèses pour plus de clarté.

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

Certaines parties nécessitent des explications supplémentaires. Dans ce programme, les exposants ⁰¹font tous deux référence au premier argument S. Cependant, si αest une fonction, alors α¹signifie "appliquer αà S", tandis que ⁰αsignifie "se connecter Sau deuxième argument de α". La fonction ¦vérifie si son premier argument contient tous les éléments du second (comptage des multiplicités), donc Sdevrait être son deuxième argument.

Dans la première partie, la fonction qui ¡utilise peut être interprétée comme S(f~Λ€∫)(×:)¹. Le combinateur Sse comporte comme Sαβγ -> (αγ)(βγ), ce qui signifie que nous pouvons le simplifier (f~Λ€∫¹)(×:¹). La deuxième partie, ×:¹est "mix with Sby prepending", et son résultat est transmis à la première partie. La première partie f~Λ€∫¹, fonctionne comme ça. La fonction ffiltre une liste par une condition, qui dans ce cas est ~Λ€∫¹. Il reçoit une liste de listes L, donc nous l'avons ~Λ€∫¹L. Le combinateur ~se comporte comme ~αβγδε -> α(βδ)(γε): le premier argument est passé à β, le second à γet les résultats sont combinés avec α. Cela signifie que nous avons Λ(€¹)(∫L). La dernière partie ∫Lest juste les sommes cumulées de L,€¹est une fonction qui vérifie l'appartenance S, Λprend une condition (ici €¹) et une liste (ici ∫L), et vérifie que tous les éléments la satisfont. En termes simples, nous filtrons les résultats du mixage en fonction de leur somme cumulée S.

Rubis , 135 octets

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

Essayez-le en ligne!

Utilisez une recherche en premier. n = 10 fonctionne sur TIO, n = 15 prend plus d'une minute, mais fonctionne sur ma machine.

Rubis , 147 octets

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

Essayez-le en ligne!

Version optimisée, fonctionne sur TIO pour n = 15 (~ 20 sec)

En fait, c'est le début d'une approche sans force brute. J'espère que quelqu'un y travaillera et trouvera une solution complète.

Premières idées:

• La somme du tableau de sortie est le dernier élément (max) du tableau d'entrée.
• La somme du tableau de sortie moins le premier (ou le dernier) élément, est l'avant-dernier élément du tableau d'entrée.
• Si un tableau est une solution, le tableau inversé est également une solution, nous pouvons donc supposer que le premier élément est la différence entre les 2 derniers éléments du tableau d'entrée.
• Le deuxième élément peut être la différence entre le deuxième et le troisième ou l'avant-dernier élément du tableau d'entrée.

Ce qui nous amène à la prochaine optimisation:

Rubis , 175 octets

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

Essayez-le en ligne!

~ 8,5 secondes sur TIO. Pas mal...

... et ainsi de suite (à mettre en œuvre)

Haskell, 117 111 octets

6 octets économisés grâce à @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

Essayez-le en ligne!

fr$S$ins

Quand nest zéro (joué au n<1), la liste doit être prête, nous vérifions donc si toutes les valeurs ont été vues. Sinon, nous retournons une liste vide pour indiquer aucune solution, sinon nous retournons une liste singleton contenant une liste vide, à laquelle les éléments choisis seront ajoutés. Ce cas aurait également pu être traité avec les équations supplémentaires

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

Si nn'est pas nul, on retourne

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

C'est la liste des (1) listes d'où provient le premier élément (2) set le reste (5) de l'appel récursif, à la condition (4) que toutes les nouvelles sommes soient dedans s. Les nouvelles sommes sont calculées en (3) - note qui test tirée d'une liste singleton, un hack de golf laid pour ce que serait Haskell idiomatique let t=y:map(y+)i. L'appel récursif (5) obtient comme nouveau rmis l'ancien sans les éléments qui apparaissent parmi les nouvelles sommes t.

La fonction principale &appelle la fonction d'aide en disant que nous devons encore voir toutes les valeurs ( r=s) et qu'il n'y a pas encore de sommes ( i=[]).

Pour sept octets supplémentaires, nous pouvons restreindre le calcul pour ne donner que le premier résultat (le cas échéant), qui est beaucoup plus rapide et gère tous les cas de test en moins de 2 secondes.

Essayez-le en ligne! (il s'agit du premier résultat uniquement une variation de l'ancienne version)

Nettoyer , 177 octets

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

Essayez-le en ligne!

Prend environ 40 secondes sur ma machine pour le n=15cas de test, mais il expire sur TIO.

Nettoyer , 297 octets

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

Essayez-le en ligne!

Celui-ci comprend quelques optimisations faites par GB ainsi que certaines des miennes. Je pense que certains d'entre eux peuvent être rendus plus génériques, alors j'ajouterai une explication une fois cela fait.

Cela prend environ 10 secondes sur ma machine, 40 secondes sur TIO.

Python 3 , 177 octets

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)

Essayez-le en ligne!

(quelques nouvelles lignes / espaces ajoutés pour éviter aux lecteurs d'avoir à faire défiler le code)

Un port direct de ma réponse Jelly (avec quelques modifications, voir la section "note" ci-dessous)

Résultat de l'exécution locale:

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

J'ai entendu que itertoolsc'était verbeux, mais ma meilleure combinationsimplémentation est encore plus verbeuse:

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]

Remarque .

• L'utilisation de division / modulo dans a[p//n:p%n+1]prend environ 2 fois plus de temps, mais économise quelques octets.
• C'est un peu différent de la réponse Jelly - la réponse Jelly réitère en arrière.
• Grâce au combinationsretour d'un itérateur, c'est plus convivial pour la mémoire.

Gelée , 35 octets

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

Essayez-le en ligne!

Exécuter localement: (n = 15 prend plus de 1 Go 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 fait, j'ai exécuté la version codée UTF8, qui prend plus de 35 octets, mais le résultat est quand même le même)

Cette solution utilise un court-circuit pour réduire le temps d'exécution.

Sans court-circuit, ce code prend environ $\binom {|S|-2}{n-2} \times \left( \frac {n^3}6 + n^2\log{n^2} \right)$ opérations, qui évalue à $\binom {26-2}{15-2} \times \left( \frac {15^3}6 + 15^2\log{15^2} \right) \approx 5.79 \times 10^9$, mais en raison de l'inefficacité de Python et Jelly, il faut une éternité pour terminer. Grâce au court-circuit, il peut se terminer beaucoup plus tôt.

Explication

Nous notons que les sommes de tous les préfixes non vides sont présentes dans l'entrée et qu'elles augmentent strictement. Nous pouvons également supposer que le plus grand et le deuxième plus grand élément sont une somme de préfixes.

Par conséquent, nous pouvons envisager toutes les façons de choisir $n-2$ éléments distincts du premier $|S|-2$ éléments (il y a $\binom {|S|-2}{n-2}$ces listes), calculer les différences consécutives pour récupérer les éléments; puis vérifiez si elle est valide naïvement (obtenez tout$n^2$sous-réseaux, calculer la somme, unifier. La longueur totale des sous-réseaux est d'environ$n^3 \over 6$)

Non testé (mais devrait avoir des performances identiques)

Gelée , 32 octets

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

Essayez-le en ligne!

Version plus inefficace (sans court-circuit):

Gelée , 27 octets

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

Essayez-le en ligne!

Pour le test n = 15, cela prend jusqu'à 2 Go de RAM et ne se termine pas après environ 37 minutes.

note : Ẇ§peut être remplacé par ÄÐƤẎ. Cela peut être plus efficace.

APL (NARS), caractères 758, octets 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 fonction G dans G x (à l'aide de la fonction H) trouverait toutes les permutations de x. La fonction d dans xdy trouve si le tableau y génère à la suite du tableau d'exercices x renvoyant une valeur booléenne. La fonction F dans x F y retournerait le tableau r de longueur x, tel que ydr est vrai (= 1) Un peu long comme implémentation, mais c'est celle-ci qui calcule tous les cas en test moins de temps ... Le dernier cas pour n = 15 il tourne 20 secondes seulement ... je dois dire que cela ne trouve pas beaucoup de solutions, retourne une seule solution (enfin il semble que oui) en moins de temps (test non exploré pour différentes entrées ...) 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