# Question:How to efficiently count the number of rows that meet some pattern?

## Question:How to efficiently count the number of rows that meet some pattern?

Maple

Let M a matrix of zeros and ones for instance.

```N := 10^5:  # This is the order of magnitude I have to consider (10^4 may be enough if L is "small")
L := 5:     # L is between 3 and 8 in practice (see context at the end of this post)
M := LinearAlgebra:-RandomMatrix(N, L, generator=0..1):```

Let C a set of colums of M and |C| the number of elements of C.
Let P a list of length |C| of  zeros and ones.

I want to count al the rows in M such that

``and`( seq( M[n, C[k]] = P[k], k = 1.. |C| ) )`

For instance

```pattern := n -> `if`(evalb(`and`(seq(S[n, C[k]]=P[k], k=1..3))), 1, 0):
t0 := time():
time()-t0
12351
0.431  # seconds
```

This code appears to be quite slow when one consider that I have to run it for all the possible choices of C and P (the contect is detailed below).

Do you have any some ideas to improve the efficiency (in terms of computational time) of this counting operation?

The context:
Let A = {1, 2, .., L} and P(A) the power set of A.
I set Q(A) = P(A) \ ( { } union A}.
Let C and C'  two disjoint subsets of Q(A).
Example

```# With L=3

Q(A) = { {1},  {2},  {3},  {1, 2},  {1, 3},  {2, 3} }

# if A chose C =
C = {2}

# Then C' is member of
C' in { {1}, {3}, {1, 3}```

For any couple (C, C')  I want to do this

1. Let |C| (|C'|) cardinal of C (resp C').

2. Let us consider that members of C (resp C') "point to" the corresponding columns of M.
for instance C = {2, 3} refers to columns 2 and 3 of M.
As C and C' are ordered iI will write them indistinctely as lists (for instance C = [2, 3] in example above) when necessary.

3. To a given |C| (|C'|) one may associate 2|C| (resp 2|C'|) sequences of 0 and 1.
For instance,  to C = {2, 3} are associated sequences [0, 0], [0, 1], [1, 0], [1, 1].
Let s(C) (s(C')) the list, or set, of 0-1 sequences associated to C (resp C')..

4. For any couple (C, C') and any of the 2|C|+|C'| combinations (p, p') where p belongs to s(C) and p' belongs to s(C') I want to count the number of occurrences defined by:
`seq( M[n, C[k]] = p[k], k=1..|C|) and seq( M[n, C'[k]] = p'[k], k=1..|C'|) `

For instance, if C={2} and C={1, 3} I want to count the number M rows M such that

```p = [0], p'=[1, 0]
M[n, 2]=0 and M[n, 1]=1 and M[n, 3]=0;

p = [1], p'=[1, 1]
M[n, 2]=1 and M[n, 1]=1 and M[n, 3]=1

... and so on```

The computational time may ne quite large because of the number of possible couples (C, C') when L is large ( there exists  Stirling2(L+1, 3) such couples: already 90 couples for L=5  ... and 28501 for L=10).

﻿