El álgebra de Steenrod es un álgebra importante que surge en la topología algebraica. El álgebra de Steenrod es generado por operadores llamados "cuadrados de Steenrod", existe uno para cada entero positivo i. Hay una base para el álgebra de Steenrod que consiste en "monomios admisibles" en las operaciones de cuadratura. Nuestro objetivo es generar esta base.

Una secuencia de enteros positivos se llama admisible si cada entero es al menos dos veces el siguiente. Entonces, por ejemplo, [7,2,1]es admisible porque $7 \geq 2*2$ y $2 \geq 2*1$ . Por otro lado, [3,2]no es admisible porque $3 < 2*2$ . (En topología escribiríamos $\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1$ para la secuencia [7,2,1]).

El grado de una secuencia es el total de sus entradas. Entonces, por ejemplo, el grado de [7,2,1]es $7 + 2 + 1 = 10$ . El exceso de una secuencia admisible es el primer elemento menos el total de los elementos restantes, por lo que [7,2,1]tiene un exceso de $7 - 2 - 1 = 4$ .

Tarea

Escriba un programa que tome un par de enteros positivos (d,e)y genere el conjunto de todas las secuencias admisibles de grado dy exceso menor o igual que e. La salida es un conjunto, por lo que el orden de las secuencias admisibles no importa.

Ejemplos:

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

Aquí estamos buscando secuencias admisibles con un total 3. Hay dos opciones, [3]y [2,1]. ( [1,1,1]y [1,2]tienen suma 3 pero no son admisibles). El exceso de [3]es 3 y el exceso de [2,1]es $2-1 = 1$ . Por lo tanto, la única secuencia con exceso de $\leq1$ es [2,1].

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

Dado que el exceso siempre es menor o igual que el grado, no tenemos condición de exceso. Por lo tanto, sólo estamos tratando de encontrar todas las secuencias admisibles de grado 6. Las opciones son [6], [5, 1]y [4, 2]. (Estos tienen un exceso de $6$ , $5-1 = 4$ y $4-2=2$ ).

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

Las secuencias admisibles de grado 10 son:

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

Estos tienen un exceso de $10$ , $9-1 = 8$ , $8-2 = 6$ , $7-3 = 4$ , $7-2-1 = 4$ y $6-3-1=2$ respectivamente, por lo que los tres últimos funcionan.

Puntuación

Este es el código de golf: la solución más corta en bytes gana.

Casos de prueba:

Cualquier reordenación de la salida es igualmente buena, por lo que para entrada (3, 3), salidas [[3],[2,1]]o [[2,1],[3]]son igualmente aceptables (sin embargo, [[1,2],[3]]no lo es).

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

Guardado 4 bytes gracias a Grimy

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

Pruébalo en línea!

Explicación

Ŝ              # 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]&

Pruébalo en línea!

-4 bytes por @attinat

• IntegerPartitions@d : Obtenga todas las listas de enteros que suman d
• Cases[,...]: Filtrar por la siguiente condición:
  • 2#& @@# - d <= e &&: Dos veces el primer elemento menos la suma es menor que e , y ...
  • Max@Ratios@#<=.5: Las proporciones de elementos sucesivos de la lista son todas inferiores a 1/2.

Como ees menor que .5, podemos convertir esto en una desigualdad encadenada.

Para algunos bytes adicionales, esto es significativamente más rápido: ¡ Pruébelo en línea!

Jalea ,  16  15 bytes

-1 gracias a Erik the Outgolfer (un ajuste inteligente a la comprobación que permite un solo filtro)

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

Un enlace diádico que acepta un número entero positivo, d , a la izquierda y un número entero positivo e, a la derecha que produce una lista de listas de números enteros positivos.

Pruébalo en línea! (el pie de página formatea los resultados para evitar listar el formato de lista implícita que Jelly hace como un programa completo)

¿Cómo?

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

1 byte guardado gracias a nimi

4 bytes guardados gracias a xnor

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

Pruébalo en línea!

JavaScript (V8) ,  88 87  81 bytes

Toma entrada como (e)(d). Imprime las secuencias en 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)

Pruébalo en línea!

Comentado

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

Pruébalo en línea!

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

Lista de comprensión gigante. Lo más probable es que no sea la mejor manera de hacer esto, pero no puedo entender cómo omitir las declaraciones 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 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)])

Pruébalo en línea!

Según las ediciones de @Jonas Ausevicius

Carbón de leña , 42 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Ｆθ⊞υ⟦⊕ι⟧

Primero cree una lista de listas de [1]..[d].

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

Para cada lista, cree nuevas listas con el prefijo de todos los números desde el primer número duplicado hasta dy agregue esas listas a la lista de listas que se procesarán. Esto asegura que todas las secuencias admisibles que contienen números no mayores que dlas creadas.

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

Salida solo aquellas listas cuyo grado es d y el exceso no es mayor que e. (La suma del grado y el exceso es igual al doble del primer número de la lista).

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*

toma d,ecomo entrada; lista de salidas de tuplas

Respuesta similar a @OrangeCherries y ayuda de los comentarios; pero más bytes guardados

Pruébalo en línea!

Jalea , 18 bytes

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

Pruébalo en línea!

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

Pruébalo en línea!