Algebra Steenrod jest ważną algebrą, która pojawia się w topologii algebraicznej. Algebra Steenroda jest generowana przez operatory zwane „kwadratami Steenroda”, po jednym dla każdej dodatniej liczby całkowitej i. Istnieje podstawa algebry Steenroda składającej się z „dopuszczalnych jednomianów” w operacjach kwadratu. Naszym celem jest wygenerowanie tej podstawy.

Sekwencja liczb całkowitych dodatnich nazywana jest dopuszczalną, jeśli każda liczba całkowita jest co najmniej dwa razy większa od następnej. Na przykład [7,2,1]jest to dopuszczalne, ponieważ $7 \geq 2*2$ i $2 \geq 2*1$ . Z drugiej strony [3,2]nie jest dopuszczalne, ponieważ $3 < 2*2$ . (W topologii zapisywalibyśmy sekwencję $\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1$[7,2,1] ).

Stopień sekwencji jest sumą go za wpisy. Na przykład stopień [7,2,1]wynosi $7 + 2 + 1 = 10$ . Nadmiar od dopuszczalnego sekwencji jest pierwszym elementem minus suma pozostałe elementy, to [7,2,1]jest nadmiar $7 - 2 - 1 = 4$ .

Zadanie

Napisz program, który bierze parę dodatnich liczb całkowitych (d,e)i wyświetla zbiór wszystkich dopuszczalnych sekwencji stopni di nadwyżek mniejszych lub równych e. Wyjście jest zbiorem, więc kolejność dopuszczalnych sekwencji nie ma znaczenia.

Przykłady:

 Input: 3,1
 Output: [[2,1]]

Tutaj szukamy dopuszczalnych sekwencji o sumie 3. Istnieją dwie opcje, [3]i [2,1]. ( [1,1,1]i [1,2]mają sumę 3, ale nie są dopuszczalne). Nadmiar [3]wynosi 3, a nadmiar [2,1]wynosi $2-1 = 1$ . Zatem jedyną sekwencją z nadmiarem $\leq1$ jest [2,1].

Input: 6, 6
Output: [[6], [5, 1], [4, 2]] (or any reordering, e.g., [[5,1],[4,2],[6]])

Ponieważ nadwyżka jest zawsze mniejsza lub równa stopniowi, nie mamy nadwyżki. Tak więc, jesteśmy po prostu staramy się znaleźć wszystkie dopuszczalne sekwencje stopni 6. opcje są [6], [5, 1]i [4, 2]. (Mają one więcej niż $6$ , $5-1 = 4$ , a $4-2=2$ ).

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

Dopuszczalne sekwencje stopnia 10 to:

[[10], [9,1], [8,2], [7,3], [7,2,1], [6,3,1]]

Mają one odpowiednio $10$ , $9-1 = 8$ , $8-2 = 6$ , $7-3 = 4$ , $7-2-1 = 4$ i $6-3-1=2$ , więc wszystkie trzy ostatnie działają.

Punktacja

To jest kod golfowy: wygrywa najkrótsze rozwiązanie w bajtach.

Przypadki testowe:

Wszelkie zmiany kolejności danych wyjściowych są równie dobre, więc dla danych wejściowych (3, 3), wyjściowych [[3],[2,1]]lub [[2,1],[3]]są równie akceptowalne (jednak [[1,2],[3]]nie są).

Input: 1, 1
Output: [[1]]

Input: 3, 3
Output: [[2,1], [3]]

Input: 3, 1
Output: [[2,1]]

Input: 6, 6
Output: [[6], [5, 1], [4, 2]]

Input: 6, 4
Output: [[5,1], [4,2]]

Input: 6, 1
Output: []

Input: 7, 7
Output: [[7], [6,1], [4,2,1], [5,2]]

Input: 7,1
Output: [[4,2,1]]

Input: 10, 10
Output: [[10], [9,1], [7,2,1], [6,3,1], [8,2], [7,3]]

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

Input: 26, 4
Output: [15, 7, 3, 1]

Input: 26, 6
Output: [[16, 7, 2, 1], [16, 6, 3, 1], [15, 7, 3, 1], [16, 8, 2], [16, 7, 3]]

05AB1E , 16 12 bajtów

Zaoszczędzone 4 bajty dzięki Grimy

Åœíʒx¦@P}ʒÆ@

Wypróbuj online!

Wyjaśnienie

Ŝ              # integer partitions
  í             # reverse each
   ʒ    }       # filter, keep only elements true under:
    x           # each element doubled
     ¦          # remove the first element in the doubled list
      @         # compare with greater than or equal with the non-doubled
       P        # product
         ʒ      # filter, keep only elements true under:
          Æ     # reduce by subtraction
           @    # compare with greater than or equal to second input

Wolfram Language (Mathematica) , 67 62 bajtów

Cases[IntegerPartitions@#,a_/;2a[[1]]-#<=#2>Max@Ratios@a<=.5]&

Wypróbuj online!

-4 bajty przez @attinat

• IntegerPartitions@d : Uzyskaj wszystkie listy liczb całkowitych sumujących się do d
• Cases[,...]: Filtruj według następującego warunku:
  • 2#& @@# - d <= e &&: Dwa razy pierwszy element minus suma jest mniejsza niż ei ...
  • Max@Ratios@#<=.5: Stosunki kolejnych elementów listy są mniejsze niż 1/2.

Ponieważ ejest mniej niż .5, możemy to zmienić w łańcuchową nierówność.

W przypadku kilku dodatkowych bajtów jest to znacznie szybsze: wypróbuj online!

Galaretka ,  16  15 bajtów

-1 dzięki Erikowi Outgolfer (inteligentne dostosowanie do sprawdzania pozwalające na pojedynczy filtr)

:Ɲ;_/>¥’Ạ
ŒṗUçƇ

Dyadyczny link akceptujący dodatnią liczbę całkowitą dpo lewej stronie i dodatnią liczbę całkowitą epo prawej stronie, która daje listę list dodatnich liczb całkowitych.

Wypróbuj online! (stopka formatuje wyniki, aby uniknąć listy niejawnego formatowania listy, którą Jelly robi jako pełny program)

W jaki sposób?

:Ɲ;_/>¥’Ạ - Link 1: admissible and within excess limit? descending list, L; excess limit, e
 Ɲ        - neighbour-wise:
:         -   integer division  -- admissible if all these are >1
      ¥   - last two links as a dyad - i.e. f(L,e):
    /     -   reduce (L) by:
   _      -     subtraction
     >    -   greater than (e)? (vectorises)  -- within excess if all these are ==0
  ;       - concatenate
       ’  - decrement (vectorises)
        Ạ - all (non-zero)?

ŒṗUçƇ - Main link: integer, d; integer, e
Œṗ    - partitions (of d)
  U   - reverse each
    Ƈ - filter keep those (v in that) for which:
   ç  -   call last Link (1) as a dyad - i.e. f(v, e)

Haskell , 59 58 54 bajtów

1 bajt zapisany dzięki nim

4 bajty zapisane dzięki xnor

0#_=[[]]
d#m=do i<-[1..div(m+d)2];(i:)<$>(d-i)#(2*i-d)

Wypróbuj online!

JavaScript (V8) ,  88 87  81 bajtów

Pobiera dane wejściowe jako (e)(d). Drukuje sekwencje do STDOUT.

e=>g=(d,s=x=d,a=[])=>s>0?d&&g(d-1,s,a,g(d>>1,s-d,[...a,d])):a[s]*2-x<=e&&print(a)

Wypróbuj online!

Skomentował

e =>                  // e = maximum excess
  g = (               // g is a recursive function taking:
    d,                //   d   = expected degree; actually used as the next candidate
                      //         term of the sequence in the code below
    s =               //   s   = current sum, initialized to d; we want it to be equal
                      //         to 0 when a sequence is complete
    x = d,            //   x   = copy of the expected degree
    a = []            //   a[] = current sequence
  ) =>                //
    s > 0 ?           // if s is positive:
      d &&            //   if d is not equal to 0:
        g(            //     outer recursive call:
          d - 1,      //       decrement d
          s,          //       leave s unchanged
          a,          //       leave a[] unchanged
          g(          //       inner recursive call:
            d >> 1,   //         update d to floor(d / 2)
            s - d,    //         subtract d from s
            [...a, d] //         append d to a[]
          )           //       end of inner recursive call
        )             //     end of outer recursive call
    :                 //   else:
      a[s] * 2 - x    //     s if either 0 (success) or negative (failure)
                      //     if s is negative, a[s] is undefined and this expression
                      //     evaluates to NaN, forcing the test to fail
      <= e            //     otherwise, we test whether the excess is valid
      && print(a)     //     and we print a[] if it is

Pyth , 23 bajty

f!>-FTvzf!<#2/MCtBT_M./

Wypróbuj online!

f!>-FTvzf!<#2/MCtBT_M./Q   Implicit: Q=input 1, vz=input 2
                           Trailing Q inferred
                     ./Q   Generate partitions of Q (ordered lists of integers which sum to Q)
                   _M      Reverse each
        f                  Filter keep elements of the above, as T, where:
               CtBT          Pair the set with itself without the first element and transpose
                             This yields all adjacent pairs of values
             /M              Integer divide each pair
           #                 Filter keep elements...
          < 2                ... less than 2
                             For admissible sequences this will be empty
         !                   Logical NOT - maps [] to true, populated lists to false
                           Result of filter are all admissible sequences
f                          Filter keep the above, as T, where:
   -FT                       Reduce T by subtraction to get degree
 !>   vz                     Is the above not greater than vz?
                           Implicit print

Python 3 , 213 bajtów

Zrozumienie gigantycznej listy. Najprawdopodobniej nie jest to najlepszy sposób na zrobienie tego, ale nie mogę wymyślić, jak pominąć instrukcje if

import itertools as z
f=lambda d,e:[c for c in [[b for b in list(z.permutations(range(1,d+1),i)) if sum(b)==d and b[0]-sum(b[1:i])<=e and all([b[i]>=b[i+1]*2 for i in range(len(b)-1)])] for i in range(1,5)] if c]

Python 3 , 172 bajty

from itertools import*
r=range
f=lambda d,e:filter(len,[[b for b in permutations(r(1,d+1),i)if d==sum(b)and~e<d-2*b[0]and all(i>=j*2for i,j in zip(b,b[1:]))]for i in r(5)])

Wypróbuj online!

Zgodnie z edycjami @Jonas Ausevicius

Węgiel drzewny , 42 bajty

Ｆθ⊞υ⟦⊕ι⟧ＦυＦ…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ιＩΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Ｆθ⊞υ⟦⊕ι⟧

Najpierw utwórz listę list z [1]..[d].

ＦυＦ…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ι

Dla każdej listy utwórz nowe listy, poprzedzając wszystkie liczby od podwojonego pierwszego numeru, di dołącz te listy do listy list do przetworzenia. Dzięki temu dtworzone są wszystkie dopuszczalne sekwencje zawierające liczby nie większe niż .

ＩΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Wyprowadzaj tylko te listy, których stopień jest di nadwyżka nie jest większa niż e. (Suma stopnia i nadwyżki jest równa dwukrotności pierwszej liczby na liście.)

Python 3 , 156 bajtów

lambda d,e:[x for y in range(5)for x in permutations(range(1,d+1),y)if all(i>=j*2for i,j in zip(x,x[1:]))and d==sum(x)and~e<d-2*x[0]]
from itertools import*

przyjmuje d,ejako dane wejściowe; wyświetla listę krotek

Podobne do @OrangeCherries odpowiedź i pomoc w komentarzach; ale więcej bajtów zostało zapisanych

Wypróbuj online!

Galaretka , 18 bajtów

ŒṗU:Ɲ’ẠƊƇUṪ_SƊ’<ʋƇ

Wypróbuj online!

Rubinowy , 78 bajtów

g=->(d,e,m=1){d<m ?[]:g[d-m,e+m,m*2].map{|q|q+[m]}+g[d,e,m+1]|(d>e ?[]:[[d]])}

Wypróbuj online!