Berechnen Sie die Anzahl der Matrizen mit entsprechenden Summen

12

Bei der Multiplikation von Monomen auf Milnor-Basis für die Steenrod-Algebra werden im Rahmen des Algorithmus bestimmte "zulässige Matrizen" aufgelistet.

Gegeben sind zwei Listen nichtnegativer Ganzzahlen r 1 , ..., r m und s 1 , ..., s n , eine Matrix nichtnegativer Ganzzahlen X

eine Matrix

ist zulässig, wenn

  1. Die Summe der j-ten Spalte ist kleiner oder gleich s j :

    Spaltensummenbeschränkung

  2. Die Summe der mit Zweierpotenzen gewichteten i-ten Zeile ist kleiner oder gleich r i :

    Zeilensummenbeschränkung

Aufgabe

Schreiben Sie ein Programm, das ein Paar Listen r 1 , ..., r m und s 1 , s 1 , ..., s n verwendet und die Anzahl der zulässigen Matrizen für diese Listen berechnet. Ihr Programm kann gegebenenfalls m und n als zusätzliche Argumente verwenden.

  • Diese Zahlen können in einem beliebigen Format eingegeben werden, zum Beispiel in Listen gruppiert oder in Unary oder irgendetwas anderem codiert.

  • Die Ausgabe sollte eine positive Ganzzahl sein

  • Es gelten Standardlücken.

Wertung

Das ist Codegolf: Kürzeste Lösung in Bytes gewinnt.

Beispiele:

Für [2]und [1]gibt es zwei zulässige Matrizen:

Beispiel 1

Für [4]und [1,1]gibt es drei zulässige Matrizen:

Beispiel 2

Für [2,4]und [1,1]gibt es fünf zulässige Matrizen:

Beispiel 3

Testfälle:

   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
Kapuze
quelle
1
IMO wäre die Definition leichter zu verstehen, wenn Sie die erste Zeile und Spalte der Matrizen verlieren, von 1 indexieren und <= anstelle von == verwenden.
Peter Taylor
Okay, wird es tun. Ich habe gerade die Definition aus einem Mathematik-Lehrbuch kopiert und sie hatte eine tatsächliche Verwendung für diese Einträge.
Hood

Antworten:

3

JavaScript (ES7), 163 Byte

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)

Testfälle

NB : Ich habe die zwei zeitaufwändigsten Testfälle aus diesem Snippet entfernt, aber sie sollten auch erfolgreich sein.

Kommentiert

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
quelle
1

Gelee , 26 Bytes

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

Ein vollständiges Programm mit S , R, das die Zählung ausgibt

Probieren Sie es online!

Wie?

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
quelle
1

Wolfram Language (Mathematica) , 101 Bytes

Lassen Sie Mathematica es als ein System von Ungleichungen über die ganzen Zahlen lösen. Ich richte ein symbolisches Array ein fund fädle drei Sätze von Ungleichungen ein. Join@@nur die Liste für abflachen Solve.

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

Probieren Sie es online!

Kelly Lowder
quelle
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]]&

Probieren Sie es online aus

Erklärung: Partitioniert jedes der r i in Potenzen von 2 und führt dann alle Tupel mit einer Zerlegung in Zweierpotenzen für jede ganze Zahl durch, subtrahiert die Spaltensummen von der Liste der s i . Zählen Sie die Anzahl der Tupel, die alle verbleibenden Einträge positiv sind.

Kapuze
quelle
2
In der Regel wird davon abgeraten, Ihre eigene Herausforderung zu beantworten, bis andere bereits in dieser Sprache eingereicht haben.
HyperNeutrino
@HyperNeutrino Ich kann es löschen, wenn Sie denken, dass das eine gute Idee ist. Das ist nicht besonders vorsichtig, also ist es sehr wahrscheinlich, dass andere es besser machen können.
Hood
3
Es ist zwar keine schlechte Sache, die Lösbarkeit zu beweisen, ich empfehle jedoch nicht, die Lösung so schnell zu verderben. Vielleicht erst eine Woche warten oder so.
Erik der Outgolfer 18.01.18
Soll ich es jetzt löschen oder lassen, nachdem ich es gepostet habe?
Hood
Ich würde es verlassen. Pace Erik Ich glaube nicht, dass es etwas verdirbt: Die Existenz einer Lösung ergibt sich aus der Tatsache, dass die Matrizen, die die Spaltensummenbeschränkung einhalten, endlich und leicht zu generieren sind.
Peter Taylor