Une séquence d'entiers est une séquence unique si la différence entre deux nombres consécutifs dans cette séquence est -1 ou 1 et son premier élément est 0.

Plus précisément: a1, a2, ..., an est une séquence unique si:

For any k (1 ≤  k < n): |a[k] - a[k+1]|=1, 
a[1]=0

Contribution

• n - nombre d'éléments dans la séquence
• s - somme des éléments de la séquence

Production

• un ensemble / liste / tableau / etc d'une séquence de longueur navec une somme d'éléments s, si possible
• un ensemble / liste / tableau / etc vide si pas possible

Exemples

Pour l'entrée 8 4, la sortie pourrait être [0 1 2 1 0 -1 0 1]ou [0 -1 0 1 0 1 2 1]. Il peut y avoir d'autres possibilités.

Pour l'entrée 3 5, la sortie est vide [], car elle ne peut pas être effectuée.

Règles

Il s'agit d'un code de golf, la réponse la plus courte en octets gagne. Les soumissions doivent être un programme ou une fonction. L'entrée / sortie peut être donnée de n'importe quelle manière standard .

CJam, 56 47 44 34 octets

Beaucoup de possibilités d'amélioration ici, mais voici la première tentative:

L0aa{{[~_(]_)2++}%}l~:N;(*{:+N=}=p

Remerciements à Dennis pour une manière efficace de faire la { ... }%partie.

Imprime la représentation du tableau si possible, sinon ""

Essayez-le en ligne ici

JavaScript (E6) 79 82

F=(n,t,
  d=n+n*~-n/4-t/2,
  l=1,
  q=[for(x of Array(n))d<n--?++l:(d+=~n,--l)]
)=>d?[]:q

Pas besoin de force brute ou d'énumération de tous les tuples.

Voir une séquence de longueur n comme n -1 étapes, chaque étape étant incrémentée ou décrémentée.
Notez que vous ne pouvez échanger qu'un incrément contre un décrément, la somme varie de 2, donc pour une longueur donnée, la somme est toujours paire ou toujours impaire.
Ayant tous les incréments, la séquence est 0, 1, 2, 3, ..., n-1 et nous savons que la somme est (n-1) * n / 2
En changeant la dernière étape, la somme change de 2, donc le la dernière étape pèse 2.
En changeant l'avant-dernière étape, la somme change par 4, donc la dernière étape pèse 4. C'est parce que l'étape successive s'appuie sur la somme partielle jusqu'à présent.
En changeant l'étape précédente, la somme change par 6, donc la dernière étape pèse 6 (pas 8, ce ne sont pas des nombres binaires).
...
Modification du premier pas pèse (n-1) * 2

Algorithme

Find the max sum (all increments)  
Find the difference with the target sum (if it's not even, no solution)  
Seq[0] is 0  
For each step  
  Compare current difference with the step weight
  if is less 
     we have an increment here, seq[i] = seq[i-1]+1 
  else 
     we have a decrement here, seq[i] = seq[i-1]-1.  
     Subtract we current weight from the current diff.
If remaining diff == 0, solution is Seq[]. Else no solution

Code non golfé

F=(len,target)=>{
  max=(len-1)*len/2
  delta = max-target
  seq = [last=0]
  sum = 0
  weight=(len-1)*2
  while (--len > 0)
  {
    if (delta >= weight)
    {
      --last
      delta -= weight;
    }
    else
    {
      ++last
    }  
    sum += last
    seq.push(last);
    weight -= 2;
  }  
  if (delta) return [];
  console.log(sum) // to verify

  return seq
}

Tester dans la console Firefox / FireBug

F(8,4)

Production

[0, -1, 0, -1, 0, 1, 2, 3]

GolfScript ( 41 39 octets)

[][1,]@~:^;({{.-1=(+.)))+}%}*{{+}*^=}?`

Démo en ligne

Merci à Dennis pour 41-> 39.

Mathematica, 73 octets

f=FirstCase[{0}~Join~Accumulate@#&/@Tuples[{-1,1},#-1],l_/;Tr@l==#2,{}]&;

Solution simple de force brute.

Je génère tous les choix d'étapes. Ensuite, je les transforme en listes accumulées pour obtenir les séquences uniques. Et puis je cherche le premier dont la somme est égale au deuxième paramètre. S'il n'y a pas, la valeur par défaut est {}.

Haskell, 56 octets

n%s=[x|x<-scanl(+)0`map`mapM(\_->[1,-1])[2..n],s==sum x]

Explication:

• Construisez une liste avec les permutations 1,-1et la longueur n-1: replicateM n-1[-1,1]
  Exemple: replicateM 2 [-1,1]==[[-1,-1],[-1,1],[1,-1],[1,1]]
• Construisez-en une séquence. scanla de mauvaises performances, mais il fait le bon travail ici.
• Filtrer toutes les séquences uniques possibles avec une longueur noù la somme ests

Python, 138

from itertools import*
def f(n,s):
 for i in[list(accumulate(x))for x in product([-1,1],repeat=n-1)]:
  if sum(i)==s:return[0]+i
 return[]

CJam, 65 58 54 octets

À peine plus courte que ma solution Mathematica, mais c'est surtout ma faute si je n'utilise toujours pas CJam correctement:

0]]l~:S;({{_1+\W+}%}*{0\{+_}%);}%_{:+S=}#_@\i=\0>\[]?p

C'est littéralement le même algorithme: obtenir tous les n-1-tuples de {1, -1}. Trouvez le premier dont l'accumulation est la même que s, ajoutez a 0. Imprime un tableau vide s'il n'en trouve aucun.

CJam, 40

Une autre approche dans CJam.

ri,W%)\_:+ri-\{2*:T1$>1{T-W}?2$+\}/])!*p

Rubis (136)

def one_sequences(n)
  n.to_s.chars.map(&:to_i).each_cons(2).to_a.select{|x|x[0] == 0 && (x[1] == 1 || x[1]
  == -1)}.count
end

J, 47 caractères

Vérifie chaque séquence comme beaucoup d'autres réponses. Va essayer de faire une solution O (n) plus courte.

   f=.4 :'(<:@#}.])(|:#~y=+/)+/\0,|:<:2*#:i.2^<:x'

   8 f 4
0 1 2 1 0 1 0 _1

   3 f 5
[nothing]

APL 38

{⊃(↓a⌿⍨⍺=+/a←+\0,⍉1↓¯1*(⍵⍴2)⊤⍳2*⍵),⊂⍬}

Exemple:

     4 {⊃(↓a⌿⍨⍺=+/a←+\0,⍉1↓¯1*(⍵⍴2)⊤⍳2*⍵),⊂⍬}8
0 1 2 1 0 1 0 ¯1

Celui-ci, comme beaucoup d'autres, force simplement toutes les combinaisons à en trouver une qui correspond, si elle n'est pas trouvée, ne renvoie rien. En fait, il essaie plusieurs fois plusieurs combinaisons pour raccourcir le code.