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 $7 \geq 2*2$ et $2 \geq 2*1$ . En revanche, [3,2]n'est pas admissible car $3 < 2*2$ . (En topologie, nous écririons $\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1$ 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 $7 - 2 - 1 = 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 $\leq1$ 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$ , $5-1 = 4$ et $4-2=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$ , $7-3 = 4$ , $7-2-1 = 4$ et $6-3-1=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]]

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

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!

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)

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!

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

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

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

Fusain , 42 octets

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

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

Ｆθ⊞υ⟦⊕ι⟧

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

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

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.

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

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

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!

Gelée , 18 octets

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

Essayez-le en ligne!

Rubis , 78 octets

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

Essayez-le en ligne!