Générer des éléments de base de l'algèbre de Steenrod

16

L'algèbre de Steenrod est une algèbre importante qui apparaît dans la topologie algébrique. L'algèbre de Steenrod est générée par des opérateurs appelés «carrés de Steenrod», un existe pour chaque entier positif i. Il y a une base pour l'algèbre de Steenrod consistant en "monômes admissibles" dans les opérations de quadrature. Notre objectif est de générer cette base.

Une séquence d'entiers positifs est dite admissible si chaque entier est au moins deux fois le suivant. Ainsi, par exemple, [7,2,1]est admissible parce que 722 et 221 . En revanche, [3,2]n'est pas admissible car 3<22 . (En topologie, nous écririons Sq7Sq2Sq1 pour la séquence [7,2,1]).

Le degré d'une séquence est le total de ses entrées. Ainsi, par exemple, le degré de [7,2,1]est 7+2+1=10 . L' excès d'une séquence admissible est le premier élément , moins le total des éléments restants, de sorte que [7,2,1]a excès 721=4 .

Tâche

Écrivez un programme qui prend une paire d'entiers positifs (d,e)et génère l'ensemble de toutes les séquences admissibles de degré det d'excès inférieur ou égal à e. La sortie est un ensemble donc l'ordre des séquences admissibles n'a pas d'importance.

Exemples:

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

Ici, nous recherchons des séquences admissibles avec un total de 3. Il y a deux options, [3]et [2,1]. ( [1,1,1]et [1,2]avoir la somme 3 mais ne sont pas admissibles). L'excès de [3]est égal à 3 et l'excès de [2,1]est 2-1=1 . Ainsi, la seule séquence avec un excès 1 est [2,1].

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

Étant donné que l'excès est toujours inférieur ou égal au degré, nous n'avons aucune condition d'excès. Ainsi, nous essayons simplement de trouver toutes les séquences admissibles de degré 6. Les options sont [6], [5, 1]et [4, 2]. (Ceux-ci ont un excès de 6 , 51=4 et 42=2 )

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

Les séquences admissibles de degré 10 sont:

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

Ceux-ci ont un excès de 10 , 9-1=8 , 8-2=6 , 73=4 , 721=4 et 631=2 respectivement, donc les trois derniers fonctionnent tous.

Notation

Voici le code golf: la solution la plus courte en octets gagne.

Cas de test:

Tout réarrangement de la sortie est également bon, donc pour l'entrée (3, 3), les sorties [[3],[2,1]]ou [[2,1],[3]]sont également acceptables (mais ce [[1,2],[3]]n'est pas le cas).

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]]
capuche
la source
1
D'accord, je vais fournir une brève explication.
Hood

Réponses:

6

05AB1E , 16 12 octets

4 octets enregistrés grâce à Grimy

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

Essayez-le en ligne!

Explication

Ŝ              # 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
la source
ćsO-est le intégré Æ.
Grimmy
À@¨Peut également l' être ¦@.
Grimmy
1
@Grimy: Oh wow, comment ai-je pu manquer ça :) Merci!
Emigna
5

Wolfram Language (Mathematica) , 67 62 octets

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

Essayez-le en ligne!

-4 octets par @attinat

  • IntegerPartitions@d : Obtenir toutes les listes d'entiers sommant à d
  • Cases[,...]: Filtrer par la condition suivante:
    • 2#& @@# - d <= e &&: Deux fois le premier élément moins la somme est inférieure à e, et ...
    • Max@Ratios@#<=.5: Les ratios des éléments successifs de la liste sont tous inférieurs à 1/2.

Parce qu'il eest inférieur à 0,5, nous pouvons transformer cela en une inégalité chaînée.

Pour quelques octets supplémentaires, c'est beaucoup plus rapide: essayez-le en ligne!

lirtosiast
la source
1
63 octets
attinat
5

Gelée ,  16  15 octets

-1 grâce à Erik l'Outgolfer (un ajustement intelligent de la vérification permettant un seul filtre)

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

Un lien dyadique acceptant un entier positif d, à gauche et un entier positif e, à droite qui donne une liste de listes d'entiers positifs.

Essayez-le en ligne!(le pied de page met en forme les résultats pour éviter la liste, le formatage de liste implicite que Jelly fait comme un programme complet)

Comment?

:Ɲ;_/>¥’Ạ - 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
la source
Vous pouvez enregistrer un octet avec une astuce intelligente . Cela peut prendre un peu de temps pour comprendre pourquoi cela fonctionne. : P
Erik the Outgolfer
@EriktheOutgolfer génial, j'avais essayé des méthodes similaires pour aligner les deux filtres (y compris la concaténation), mais tout sortait à 16 car je ne pensais pas à utiliser l'astuce de décrémentation en même temps.
Jonathan Allan
4

Haskell , 59 58 54 octets

1 octet économisé grâce à nimi

4 octets économisés grâce à xnor

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

Essayez-le en ligne!

Post Rock Garf Hunter
la source
1
Vous pouvez économiser quelques octets en définissant #directement: Essayez-le en ligne!
xnor
3

JavaScript (V8) ,  88 87  81 octets

Prend l'entrée comme (e)(d). Imprime les séquences dans 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)

Essayez-le en ligne!

Commenté

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
la source
3

Pyth , 23 octets

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

Essayez-le en ligne!

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
la source
3

Python 3 , 213 octets

Compréhension des listes géantes. Ce n'est probablement pas la meilleure façon de le faire, mais je ne sais pas comment ignorer les instructions 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 octets

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

Essayez-le en ligne!

Selon les révisions de @Jonas Ausevicius

OrangeCherries
la source
2
Bienvenue sur le site. Quelques conseils: il semble que vous ne connaissiez pas très bien où l'espacement est requis en python. Vous avez deux ou trois endroits où les espaces pourraient être supprimés très bien, alors j'examinerais cela. Des fonctions comme allpeuvent également prendre un générateur, vous pouvez donc simplement le faire à la all(...)place de all([...]). Enfin, puisque votre soumission est une fonction totalement anonyme, vous n'êtes pas pénalisé pour l'affectation ( f=) et pouvez donc la déduire de votre score (-2 octets).
Post Rock Garf Hunter
Oh et aussi en python3, vous pouvez caster pour lister avec [*(...)]au lieu de list(...)qui enregistre généralement un octet mais dans votre cas enregistre 2 car il vous permet également de supprimer un espace.
Post Rock Garf Hunter
2
189 octets s'il est correct de renvoyer un objet filtre, sinon 192 avec [*filter(...)]. Bienvenue également :)
Réinstallez Monica le
2
172 octets
Jonas Ausevicius
2

Fusain , 42 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

Fθ⊞υ⟦⊕ι⟧

Créez d'abord une liste de listes à partir de [1]..[d].

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

Pour chaque liste, créez de nouvelles listes en préfixant tous les numéros du premier nombre doublé jusqu'à det ajoutez ces listes à la liste des listes à traiter. Cela garantit que toutes les séquences admissibles contenant des nombres non supérieurs à ceux dcréés sont créées.

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

N'afficher que les listes dont le degré est det l'excès n'est pas supérieur à e. (La somme du degré et de l'excès est égale au double du premier nombre de la liste.)

Neil
la source
2

Python 3 , 156 octets

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*

prend d,een entrée; affiche la liste des tuples

Semblable à la réponse @OrangeCherries et à l'aide des commentaires; mais plus d'octets enregistrés

Essayez-le en ligne!

Jonas Ausevicius
la source