Die Steenrod-Algebra ist eine wichtige Algebra in der algebraischen Topologie. Die Steenrod-Algebra wird von Operatoren erzeugt, die "Steenrod-Quadrate" genannt werden. Für jede positive ganze Zahl i existiert eine. Es gibt eine Grundlage für die Steenrod-Algebra, die aus "zulässigen Monomen" in den Quadrierungsoperationen besteht. Es ist unser Ziel, diese Basis zu schaffen.

Eine Folge positiver Ganzzahlen heißt zulässig, wenn jede Ganzzahl mindestens doppelt so groß ist wie die nächste. So ist zum Beispiel und[7,2,1] zulässig . Ist dagegen nicht zulässig, da . (In der Topologie schreiben wir für die Sequenz ).$7 \geq 2*2$$2 \geq 2*1$[3,2]$3 < 2*2$$\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1$[7,2,1]

Der Grad einer Sequenz ist die Summe ihrer Einträge. So zum Beispiel für den Grad [7,2,1]ist . Der Überschuss einer zulässigen Folge ist das erste Element abzüglich der Summe der verbleibenden Elemente, hat also den Überschuss .$7 + 2 + 1 = 10$7 - 2 - 1 = 4[7,2,1]$7 - 2 - 1 = 4$

Aufgabe

Schreiben Sie ein Programm, das ein Paar positiver Ganzzahlen verwendet (d,e)und die Menge aller zulässigen Folgen von Grad dund Exzess kleiner oder gleich ausgibt e. Die Ausgabe ist eine Menge, sodass die Reihenfolge der zulässigen Sequenzen keine Rolle spielt.

Beispiele:

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

Hier suchen wir nach zulässigen Folgen mit insgesamt 3. Es gibt zwei Möglichkeiten, [3]und [2,1]. ( [1,1,1]und [1,2]haben die Summe 3, sind aber nicht zulässig). Der Überschuss von [3]ist 3 und der Überschuss von [2,1]ist . Somit ist die einzige Folge mit überschüssigem ist .$2-1 = 1$$\leq1$[2,1]

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

Da der Überschuss immer kleiner oder gleich dem Grad ist, haben wir keine Überschussbedingung. So versuchen wir einfach alle zulässigen Sequenzen von Grad 6. Die Optionen zu finden sind [6], [5, 1]und [4, 2]. (Diese haben einen Überschuss von , und )$6$$5-1 = 4$$4-2=2$

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

Die zulässigen Folgen des Grades 10 sind:

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

Diese haben überschüssige , , , , 7 - 2 - 1 = 4 und 6 - 3 - 1 = 2 sind, so dass die letzten drei funktionieren.$10$$9-1 = 8$$8-2 = 6$$7-3 = 4$$7-2-1 = 4$$6-3-1=2$

Wertung

Das ist Codegolf: Kürzeste Lösung in Bytes gewinnt.

Testfälle:

Jede Neuordnung der Ausgabe ist gleichermaßen gut, also für Eingaben (3, 3), Ausgaben [[3],[2,1]]oder [[2,1],[3]]sind gleichermaßen akzeptabel (ist es aber [[1,2],[3]]nicht).

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 Bytes

4 Bytes dank Grimy gespart

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

Probieren Sie es online!

Erläuterung

Ŝ              # 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 Bytes

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

Probieren Sie es online!

-4 Bytes von @attinat

• IntegerPartitions@d : Erhalte alle Listen von ganzen Zahlen, die zu summieren sind d
• Cases[,...]: Nach folgender Bedingung filtern:
  • 2#& @@# - d <= e &&: Zweimal das erste Element minus die Summe ist kleiner als e, und ...
  • Max@Ratios@#<=.5: Alle Verhältnisse aufeinanderfolgender Elemente der Liste sind kleiner als 1/2.

Weil ekleiner als 0,5 ist, können wir daraus eine verkettete Ungleichung machen.

Für ein paar zusätzliche Bytes ist dies erheblich schneller: Probieren Sie es online aus!

Jelly ,  16  15 Bytes

-1 dank Erik the Outgolfer (eine kluge Anpassung der Prüfung, die einen einzelnen Filter erlaubt)

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

Eine dyadische Verknüpfung d, die links eine positive Ganzzahl und erechts eine positive Ganzzahl akzeptiert und eine Liste mit Listen positiver Ganzzahlen liefert.

Probieren Sie es online! (In der Fußzeile werden die Ergebnisse formatiert, um zu vermeiden, dass die implizite Listenformatierung, die Jelly als vollständiges Programm ausführt, angezeigt wird.)

Wie?

:Ɲ;_/>¥’Ạ - 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 Bytes

Dank nimi 1 Byte gespart

4 Bytes gespart dank xnor

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

Probieren Sie es online!

JavaScript (V8) ,  88 87  81 Bytes

Übernimmt die Eingabe als (e)(d). Druckt die Sequenzen nach 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)

Probieren Sie es online!

Kommentiert

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 Bytes

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

Probieren Sie es 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 Bytes

Riesenlistenverständnis. Höchstwahrscheinlich nicht der beste Weg, dies zu tun, aber ich kann nicht herausfinden, wie die if-Anweisungen übersprungen werden

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 Bytes

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

Probieren Sie es online!

Nach Angaben von @Jonas Ausevicius

Holzkohle , 42 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

Ｆθ⊞υ⟦⊕ι⟧

Erstellen Sie zunächst eine Liste von Listen aus [1]..[d].

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

Erstellen Sie für jede Liste neue Listen, indem Sie allen Nummern von der doppelten ersten Nummer bis das dPräfix voranstellen und diese Listen an die Liste der zu verarbeitenden Listen anhängen. Dies stellt sicher, dass alle zulässigen Folgen, die Zahlen enthalten, die nicht größer als dsind, erstellt werden.

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

Geben Sie nur die Listen aus, deren Grad dund Überschuss nicht größer als ist e. (Die Summe aus Grad und Selbstbeteiligung entspricht dem Doppelten der ersten Nummer der Liste.)

Python 3 , 156 Bytes

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*

nimmt d,eals Eingabe; gibt eine Liste von Tupeln aus

Ähnlich wie bei @OrangeCherries antworten und helfen Kommentare; aber mehr Bytes gespeichert

Probieren Sie es online!

Jelly , 18 Bytes

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

Probieren Sie es online!

Ruby , 78 Bytes

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

Probieren Sie es online!