Generar elementos básicos del álgebra de Steenrod.

16

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 722 y 221 . Por otro lado, [3,2]no es admisible porque 3<22 . (En topología escribiríamos Sq7 7Sq2Sq1 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 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 7-2-1=4 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 1 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 6 , 5 5-1=4 4 y 4 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 9-1=8 , 8-2=6 6 , 7 7-3=4 4 , 7 7-2-1=4 4 y 6 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]]
capucha
fuente
1
Bien, daré una breve explicación.
Campana de

Respuestas:

6

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
Emigna
fuente
ćsO-es el incorporado Æ.
Grimmy
También À@¨puede ser ¦@.
Grimmy
1
@Grimy: Oh, wow, ¿cómo me perdí eso :) Gracias!
Emigna
5

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!

lirtosiast
fuente
1
63 bytes
attinat
5

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)
Jonathan Allan
fuente
Puede guardar un byte con un truco inteligente . Puede tomar un poco de tiempo entender por qué eso funciona. : P
Erik the Outgolfer
@EriktheOutgolfer increíble, había intentado algunas formas similares para alinear los dos filtros (incluida la concatenación), pero todo salía como 16 ya que no pensé en emplear el truco de disminución al mismo tiempo.
Jonathan Allan
4

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!

Post Rock Garf Hunter
fuente
1
Puede guardar algunos bytes definiendo #directamente: ¡ Pruébelo en línea!
xnor
3

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

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

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

Cerezas Naranjas
fuente
2
Bienvenido al sitio. Algunos consejos: Parece que no estás muy familiarizado con el lugar donde se requiere el espacio en Python. Tienes un par de lugares donde los espacios se pueden eliminar muy bien, así que lo investigaría. También funciones como allpuede tomar un generador, por lo que puede hacer en all(...)lugar de all([...]). Por último, dado que su envío es una función completamente anónima, no se le penaliza por la asignación ( f=) y, por lo tanto, puede deducirlo de su puntaje (-2 bytes).
Post Rock Garf Hunter
Ah, y también en python3 puede lanzar a la lista en [*(...)]lugar de lo list(...)cual generalmente guarda un byte, pero en su caso guarda 2, ya que también le permite eliminar un espacio.
Post Rock Garf Hunter
2
189 bytes si está bien devolver un objeto de filtro, de lo contrario 192 con [*filter(...)]. También bienvenido :)
Reinstale a Monica el
2
172 bytes
Jonas Ausevicius
2

Carbón de leña , 42 bytes

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

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

Fθ⊞υ⟦⊕ι⟧

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

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

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.

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

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

Neil
fuente
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*

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!

Jonas Ausevicius
fuente