Calcular el número de matrices con sumas apropiadas

12

Al multiplicar monomios en la base de Milnor para el álgebra de Steenrod, parte del algoritmo implica enumerar ciertas "matrices permitidas".

Dadas dos listas de números enteros no negativos r 1 , ..., r m y s 1 , ..., s n , una matriz de números enteros no negativos X

una matriz

es permisible si

  1. La suma de la columna j es menor o igual que s j :

    restricción de sumas de columna

  2. La suma de la i-ésima fila ponderada por potencias de 2 es menor o igual que r i :

    restricción de sumas de fila

Tarea

Escribir un programa que tiene un par de listas r 1 , ..., r m y es 1 , s 1 , ..., s n y calcula el número de matrices permisibles para estas listas. Su programa puede tomar opcionalmente myn como argumentos adicionales si es necesario.

  • Estos números pueden ingresarse en cualquier formato que le guste, por ejemplo, agrupados en listas o codificados en unario, o cualquier otra cosa.

  • La salida debe ser un entero positivo

  • Se aplican lagunas estándar.

Puntuación

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

Ejemplos:

Para [2]y [1], hay dos matrices permitidas:

Ejemplo 1

Para [4]y [1,1]hay tres matrices permitidas:

ejemplo 2

Para [2,4]y [1,1]hay cinco matrices permitidas:

ejemplo 3

Casos de prueba:

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

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

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

   Input: [2,4], [1,1]   
   Output: 5      

   Input: [3,5,7], [1,2]
   Output: 14

   Input: [7, 10], [1, 1, 1]
   Output: 15       

   Input: [3, 6, 16, 33], [0, 1, 1, 1, 1]
   Output: 38      

   Input: [7, 8], [3, 3, 1]
   Output: 44

   Input: [2, 6, 15, 18], [1, 1, 1, 1, 1]
   Output: 90       

   Input: [2, 6, 7, 16], [1, 3, 2]
   Output: 128

   Input: [2, 7, 16], [3, 3, 1, 1]
   Output: 175
capucha
fuente
1
En mi opinión, la definición sería más fácil de entender si pierde la primera fila y columna de las matrices, indexa desde 1 y usa <= en lugar de ==.
Peter Taylor
Esta bien, lo haré. Acabo de copiar la definición de un libro de texto de matemáticas y tenía un uso real para esas entradas.
Hood

Respuestas:

3

JavaScript (ES7), 163 bytes

f=([R,...x],s)=>1/R?[...Array(R**s.length)].reduce((k,_,n)=>(a=s.map((_,i)=>n/R**i%R|0)).some(c=>(p+=c<<++j)>R,p=j=0)?k:k+f(x,s.map((v,i)=>v-a[i])),0):!/-/.test(s)

Casos de prueba

NB : eliminé los dos casos de prueba más largos de este fragmento, pero también deberían pasar.

Comentado

f = (                               // f = recursive function taking:
  [R,                               //   - the input array r[] splitted into:
      ...x],                        //     R = next element / x = remaining elements
  s                                 //   - the input array s[]
) =>                                //
  1 / R ?                           // if R is defined:
    [...Array(R**s.length)]         //   for each n in [0, ..., R**s.length - 1],
    .reduce((k, _, n) =>            //   using k as an accumulator:
      (a =                          //     build the next combination a[] of
        s.map((_, i) =>             //     N elements in [0, ..., R - 1]
          n / R**i % R | 0          //     where N is the length of s[]
        )                           //
      ).some(c =>                   //     for each element c in a[]:
        (p += c << ++j)             //       increment j; add c * (2**j) to p
        > R,                        //       exit with a truthy value if p > R
        p = j = 0                   //       start with p = j = 0
      ) ?                           //     end of some(); if truthy:
        k                           //       just return k unchanged
      :                             //     else:
        k +                         //       add to k the result of
        f(                          //       a recursive call to f() with:
          x,                        //         the remaining elements of r[]
          s.map((v, i) => v - a[i]) //         s[] updated by subtracting the values of a[]
        ),                          //       end of recursive call
      0                             //     initial value of the accumulator k
    )                               //   end of reduce()
  :                                 // else:
    !/-/.test(s)                    //   return true if there's no negative value in s[]
Arnauld
fuente
1

Jalea , 26 bytes

UḄ€Ḥ>⁴
0rŒpṗ⁴L¤µS>³;ÇẸµÐḟL

Un programa completo que toma S , R que imprime el recuento

Pruébalo en línea!

¿Cómo?

UḄ€Ḥ>⁴ - Link 1, row-wise comparisons: list of lists, M
U      - upend (reverse each)
 Ḅ€    - convert €ach from binary (note bit-domain is unrestricted, e.g. [3,4,5] -> 12+8+5)
   Ḥ   - double (vectorises) (equivalent to the required pre-bit-shift by one)
     ⁴ - program's 2nd input, R
    >  - greater than? (vectorises)

0rŒpṗ⁴L¤µS>³;ÇẸµÐḟL - Main link: list S, list R
0r                  - inclusive range from 0 to s for s in S
  Œp                - Cartesian product of those lists
       ¤            - nilad followed by link(s) as a nilad:
     ⁴              -   program's 2nd input, R
      L             -   length
    ṗ               - Cartesian power = all M with len(R) rows & column values in [0,s]
        µ      µÐḟ  - filter discard if:
         S          -   sum (vectorises) = column sums
           ³        -   program's 1st input, S
          >         -   greater than? (vectorises) = column sum > s for s in S
             Ç      -   call the last link (1) as a monad = sum(2^j × row) > r for r in R
            ;       -   concatenate
              Ẹ     -   any truthy?
                  L - length
Jonathan Allan
fuente
1

Wolfram Language (Mathematica) , 101 bytes

Deje que Mathematica lo resuelva como un sistema de desigualdades sobre los enteros. Configuré una matriz simbólica fy entrelacé tres conjuntos de desigualdades. Join@@Sólo se aplana la lista de Solve.

Length@Solve[Join@@Thread/@{Tr/@(t=f~Array~{q=(l=Length)@#2,l@#})<=#2,2^[email protected]<=#,t>=0},Integers]&

Pruébalo en línea!

Kelly Lowder
fuente
0

Mathematica 139 bytes

Tr@Boole[k=Length[a=#]+1;AllTrue[a-Rest[##+0],#>=0&]&@@@Tuples[BinCounts[#,{2r~Prepend~0}]&/@IntegerPartitions[#,All,r=2^Range@k/2]&/@#2]]&

Pruébalo en línea

Explicación: Divide cada r i en potencias de 2 y luego hace todas las tuplas con una descomposición en potencias de dos para cada número entero, resta los totales de columna de la lista de s i . Cuente el número de tuplas que hacen que todas las entradas restantes sean positivas.

capucha
fuente
2
por lo general, se desaconseja responder a su propio desafío hasta que otros ya lo hayan enviado en ese idioma.
HyperNeutrino
@HyperNeutrino Puedo eliminarlo si crees que es una buena idea. Esto no se juega con mucho cuidado, por lo que es muy probable que otros puedan hacerlo mejor.
Hood
3
Si bien no es malo poder demostrar que es solucionable, no recomiendo estropear la solución tan rápido. Tal vez espere una semana primero o algo así.
Erik the Outgolfer
Entonces, ¿debería eliminarlo o dejarlo ahora que lo publiqué?
Hood
Lo dejaría Pace Erik No creo que estropee nada: la existencia de una solución es obvia por el hecho de que las matrices que respetan la restricción de suma de columnas son finitas y fáciles de generar.
Peter Taylor