Generieren Sie Basiselemente der Steenrod-Algebra

16

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 ).722221[3,2]3<22Sq7Sq2Sq1[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=107 - 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=11[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 )65-1=44-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.109-1=88-2=67-3=47-2-1=46-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]]
Kapuze
quelle
1
Okay, ich werde eine kurze Erklärung geben.
Hood

Antworten:

6

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
Emigna
quelle
ćsO-ist das eingebaute Æ.
Grimmy
Auch À@¨kann ¦@.
Grimmy
1
@Grimy: Oh wow, wie habe ich das vermisst :) Danke!
Emigna
5

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!

Lirtosiast
quelle
1
63 Bytes
Attinat
5

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)
Jonathan Allan
quelle
Sie können ein Byte mit einem cleveren Trick speichern . Es kann eine Weile dauern, um zu verstehen, warum das funktioniert. : P
Erik der Outgolfer
@EriktheOutgolfer genial, ich hatte einige ähnliche Methoden versucht, um die beiden Filter (einschließlich Verkettung) inline zu setzen, aber alles wurde als 16 ausgegeben, da ich nicht daran dachte, den Dekrement-Trick gleichzeitig anzuwenden.
Jonathan Allan
4

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!

Weizen-Assistent
quelle
1
Sie können einige Bytes sparen, indem Sie #direkt definieren : Probieren Sie es online aus!
7.
3

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
Arnauld
quelle
3

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
Sok
quelle
3

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

Orangenkirschen
quelle
2
Willkommen auf der Seite. Ein paar Tipps: Ich sehe so aus, als wüssten Sie nicht genau, wo Abstand in Python erforderlich ist. Sie haben ein paar Stellen, an denen Leerzeichen entfernt werden könnten, also würde ich das untersuchen. Auch wie Funktionen allkönnen einen Generator nehmen , so dass Sie nur tun können , all(...)statt all([...]). Da es sich bei Ihrer Einreichung um eine vollständig anonyme Funktion handelt, werden Sie für die Zuweisung ( f=) nicht bestraft und können sie daher von Ihrer Punktzahl (-2 Byte) abziehen.
Weizen-Assistent
Oh, und auch in python3 können Sie in eine Liste umwandeln, mit [*(...)]der in list(...)der Regel ein Byte gespeichert wird , in Ihrem Fall jedoch 2, da Sie damit auch ein Leerzeichen entfernen können.
Wheat Wizard
2
189 Bytes, wenn es in Ordnung ist, ein Filterobjekt zurückzugeben, andernfalls 192 mit [*filter(...)]. Auch willkommen :)
Reinstate Monica
2
172 Bytes
Jonas Ausevicius
2

Holzkohle , 42 Bytes

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

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

Fθ⊞υ⟦⊕ι⟧

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

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

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.

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

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

Neil
quelle
2

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!

Jonas Ausevicius
quelle