Sekwencja liczb całkowitych jest jedną sekwencją, jeśli różnica między dowolnymi dwiema kolejnymi liczbami w tej sekwencji wynosi -1 lub 1, a jej pierwszym elementem jest 0.

Mówiąc dokładniej: a1, a2, ..., an jest jedną sekwencją, jeśli:

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

Wejście

• n - liczba elementów w sekwencji
• s - suma elementów w sekwencji

Wynik

• zestaw / lista / tablica / itd. o jednej sekwencji nz sumą elementów s, jeśli to możliwe
• pusty zestaw / lista / tablica / etc, jeśli nie jest to możliwe

Przykłady

Dla danych wejściowych 8 4wyjściem może być [0 1 2 1 0 -1 0 1]lub [0 -1 0 1 0 1 2 1]. Mogą istnieć inne możliwości.

W przypadku danych wejściowych dane 3 5wyjściowe są puste [], ponieważ nie można tego zrobić.

Zasady

To jest golfowy kod, wygrywa najkrótsza odpowiedź w bajtach. Zgłoszenia powinny być programem lub funkcją. Wejścia / wyjścia można podać na dowolny ze standardowych sposobów .

CJam, 56 47 44 34 bajtów

Tutaj jest wiele możliwości ulepszeń, ale oto pierwsza próba:

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

Podziękowania dla Dennisa za efektywny sposób wykonania { ... }%części.

Drukuje reprezentację tablicy, jeśli to możliwe, w przeciwnym razie ""

Wypróbuj online tutaj

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

Nie ma potrzeby brutalnej siły ani liczenia wszystkich krotek.

Zobacz sekwencję długości n jako n -1 kroków, przy czym każdy krok jest przyrostowy lub malejący.
Zauważ, że możesz zamienić przyrost tylko na zmniejszenie, suma zmienia się o 2, więc dla każdej długości suma jest zawsze parzysta lub zawsze nieparzysta.
Mając wszystkie przyrosty, sekwencja wynosi 0, 1, 2, 3, ..., n-1 i wiemy, że suma wynosi (n-1) * n / 2
Zmieniając ostatni krok, suma zmienia się o 2, więc ostatni krok waży 2.
Zmieniając następny na ostatni krok, suma zmienia się o 4, więc ostatni krok waży 4. To dlatego, że kolejny krok opiera się na częściowej sumie.
Zmieniając poprzedni krok, suma zmienia się o 6, więc ostatni krok waży 6 (nie 8, to nie są liczby binarne).
...
Zmiana pierwszego kroku waży (n-1) * 2

Algorytm

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

Nieskluczony kod

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
}

Przetestuj w konsoli Firefox / FireBug

F(8,4)

Wynik

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

GolfScript ( 41 39 bajtów)

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

Demo online

Dzięki Dennis za 41-> 39.

Mathematica, 73 bajty

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

Proste rozwiązanie brutalnej siły.

Generuję wszystkie opcje kroków. Następnie przekształcam je w skumulowane listy, aby uzyskać sekwencje jednoelementowe. A potem szukam pierwszego, którego suma jest równa drugiemu parametrowi. Jeśli nie, wartością domyślną jest {}.

Haskell, 56 bajtów

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

Wyjaśnienie:

• Zbuduj listę z permutacjami 1,-1i długością n-1: replicateM n-1[-1,1]
  Przykład: replicateM 2 [-1,1]==[[-1,-1],[-1,1],[1,-1],[1,1]]
• Zbuduj z niego jedną sekwencję. scanlma słabą wydajność, ale tutaj robi dobrą robotę.
• Filtruj wszystkie możliwe sekwencje z długością, ngdzie suma jests

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 bajtów

Nieco krótszy niż moje rozwiązanie Mathematica, ale to głównie moja wina, że ​​nadal nie używam CJam poprawnie:

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

Jest to dosłownie ten sam algorytm: pobierz wszystkie n-1pary {1, -1}. Znajdź pierwszy której kumulacja jest taka sama jak si przedrostek 0. Wydrukuj pustą tablicę, jeśli nie zostanie znaleziona.

CJam, 40

Inne podejście w CJam.

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

Rubin (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 znaków

Sprawdza każdą sekwencję jak wiele innych odpowiedzi. Spróbuje stworzyć krótsze rozwiązanie O (n).

   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*⍵),⊂⍬}

Przykład:

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

Ten, jak wiele innych, po prostu przebija siły przez każdą kombinację, aby znaleźć taką, która pasuje, jeśli nie zostanie znaleziona, nic nie zwraca. W rzeczywistości kilkakrotnie próbuje niektórych kombinacji, aby skrócić kod.