Efficient way to iterate over large list and check conditions

Question

The problem I am trying to solve is how to assign charges to a number of particles based on some conditions on the charges. It is conceptually very simple but requires processing a very large list. There are four possible charges: (0,1,2,3), assigned to 19 particles, so there are a total of $4^{19}$ lists of length 19 to loop over. My current attempt uses

Length[Select[Tuples[{0, 1, 2, 3}, 19], C1]]

(C1 is some condition), which seems to store all the lists in memory and crashes my computer. Since I only require to check how many possible assignments meet the required condition, I don't need to store any list in memory. What is the most efficient way to iterate over this very large list and solve the problem in a reasonable amount of time? Thanks in advance.

ps. The conditions I want to check are simple conditions like the last three particles having the same charge or the sum of charges of some particles add to zero. For example, C1 is

C1[charges_]:=Equal@@charges[[{-1,-2,-3}]]

This is a simple case that can be calculated by hand, but I am trying to combine multiple conditions that make it hard to do so.

Answer 1

Assuming your criterion functions depend on only a small subset of 19 indices, and that they apply symmetrically to columns (i.e., the number of times a condition cond is satisfied on the columns 10, 15, and 19 is the same as the number of times cond is satisfied on columns 1, 2 and 3 or on any triple of columns) you can write them as functions that take smaller lists as arguments and use Tuples (with the number of arguments in the criterion function as the second argument of Tuples).

For example:

C1[charges_] := Equal @@ charges[[-3 ;;]]
C2[charges_] := Total[charges[[{1, 3, 7, 9}]]] == 5
C3[charges_] := Total[charges[[{1, 9}]]] == 2 Total[charges[[{7, 8, 10}]]]
C4[charges_] := Mean[charges[[{1, 8}]]] == Mean[charges[[{7, 8, 9}]]]
C5[charges_] := {1, 2, 10}.charges[[{1, 2, 10}]] == 31

You can re-write C1 thru C5 as follows

c1 = Equal@@#&;
k1 = 3;
c2 = Total[#] == 5 &; 
k2 = 4;
c3 = Total[#[[;; 2]]] == 2 Total[#[[3 ;; 5]]] &;
k3 = 5;
c4 = Mean[#[[{1, 2}]]] == Mean[#[[{3, 2, 4}]]] &;
k4 = 4;
c5 = {1, 2, 10}.#[[{1, 2, 3}]] == 31 &; 
k5 = 3;

To find the number of 19-tuples that satisfy Cj we use cj to find the number kj-tuples that satisfy cj (where kj is the number of parameters in cj) and multiply it with 4^(19-kj) (this is the number of ways the 19-kj free columns can be formed):

t = 19;
Length[Select[Tuples[{0, 1, 2, 3}, k1], c1]] 4^(t - k1)

17179869184

Length[Select[Tuples[{0, 1, 2, 3}, k2], c2]] 4^(t - k2)

42949672960

Length[Select[Tuples[{0, 1, 2, 3}, k3], c3]] 4^(t - k3)

10200547328

Length[Select[Tuples[{0, 1, 2, 3}, k4], c4]] 4^(t - k4)

21474836480

Length[Select[Tuples[{0, 1, 2, 3}, k5], c5]] 4^(t - k5)

4294967296

Timings: for t = 10 (version 9.0 / Windows10 / 64bit):

t = 10;
Length[Select[Tuples[Range[0, 3], t], C1]] // AbsoluteTiming
Length[Select[Tuples[Range[0, 3], k1], c1]] 4^(t - k1) // AbsoluteTiming

{2.473403, 65536}

{0., 65536}

Length[Select[Tuples[Range[0, 3], t], C2]] // AbsoluteTiming
Length[Select[Tuples[Range[0, 3], k2], c2]] 4^(t - k2) // AbsoluteTiming

{2.258324, 163840}

{0., 163840}

Length[Select[Tuples[Range[0, 3], t], C3]] // AbsoluteTiming
Length[Select[Tuples[Range[0, 3], k3], c3]] 4^(t - k3) // AbsoluteTiming

{3.981313, 38912}

{0.003997, 38912}

Length[Select[Tuples[Range[0, 3], t], C4]] // AbsoluteTiming
Length[Select[Tuples[Range[0, 3], k4], c4]] 4^(t - k4) // AbsoluteTiming

{3.709981, 81920}

{0., 81920}

Length[Select[Tuples[Range[0, 3], t], C5]] // AbsoluteTiming
Length[Select[Tuples[Range[0, 3], k5], c5]] 4^(t - k5) // AbsoluteTiming

{2.311667, 16384}

{0., 16384}

Answer 2

Since you mention that you want to compute the total number of possibilities with multiple conditions, and that the conditions consist of equality conditions and total conditions, you might want to try using SatisfiabilityCount. Since the particles have 4 states, each particle state can be represented by a pair of booleans. For example:

$$\begin{array}{l} 0\leftrightarrow \{F,F\} \\ 1\leftrightarrow \{F,T\} \\ 2\leftrightarrow \{T,F\} \\ 3\leftrightarrow \{T,T\} \\ \end{array}$$

So, with no conditions we have:

vars = Join[Array[a, 19], Array[b, 19]];
SatisfiabilityCount[True, vars]

274877906944

or

4^19

274877906944

as expected. For the condition that the last three states are identical:

SatisfiabilityCount[
    Equivalent[a[17], a[18], a[19]] && Equivalent[b[17], b[18], b[19]],
    vars
]

17179869184

For the condition that the sum of the first 4 particle states is 5:

SatisfiabilityCount[
    Or[
        And[
            BooleanCountingFunction[{1}, 4][a[1], a[2], a[3], a[4]],
            BooleanCountingFunction[{2}, 4][b[1], b[2], b[3], b[4]]
        ],
        And[
            BooleanCountingFunction[{3}, 4][a[1], a[2], a[3], a[4]],
            BooleanCountingFunction[{1}, 4][b[1], b[2], b[3], b[4]]
        ]
    ],
    vars
]

42949672960

In order to combine conditions, it will be convenient to have a function that converts equality and total conditions into the equivalent boolean versions. Let each particle be given the name p[n]. Then, a function that converts conditions to equivalent boolean versions is:

toBool[Verbatim[Equal][x__p]] := Equivalent @@ apart[{x}] && Equivalent @@ bpart[{x}]
toBool[Verbatim[Plus][x__p] == i_Integer] := With[
    {len = Length[{x}], ap = Sequence@@apart[{x}], bp = Sequence@@bpart[{x}]},
    Or @@ Table[
        BooleanCountingFunction[{j}, len][ap] &&
        BooleanCountingFunction[{(i-j)/2}, len][bp],
        {j, Mod[i,2], i, 2}
    ]
]

apart[{x__p}] := Apply[a, {x}, {1}]
bpart[{x__p}] := Apply[b, {x}, {1}]

It is possible to add other kinds of conditions (e.g., p[1] + 2 p[2] + 3 p[3] == 6) if desired.

Repeating my previous examples:

SatisfiabilityCount[toBool[p[17] == p[18] == p[19]], vars]
SatisfiabilityCount[toBool[p[1] + p[2] + p[3] + p[4] == 5], vars]

17179869184

42949672960

Here's a more complicated version, designed to produce a low enough count that I can show each of the instances:

SatisfiabilityCount[
    toBool[Sum[p[i], {i, 1, 19, 2}] == 4] &&
    toBool[Sum[p[i], {i, 2, 18, 2}] == 2] &&
    toBool[p[1] == p[2] == p[3] == p[4] == p[5] == p[6]] &&
    toBool[p[10] == p[11] == p[12] == p[13] == p[14] == p[15]] &&
    toBool[p[16] + p[17] + p[18] + p[19] == 6],
    vars
]

9

If you want to find the set of values for the p[n] corresponding to the above counts you can use:

bools = SatisfiabilityInstances[
    toBool[Sum[p[i], {i, 1, 19, 2}] == 4] &&
    toBool[Sum[p[i], {i, 2, 18, 2}] == 2] &&
    toBool[p[1] == p[2] == p[3] == p[4] == p[5] == p[6]] &&
    toBool[p[10] == p[11] == p[12] == p[13] == p[14] == p[15]] &&
    toBool[p[16] + p[17] + p[18] + p[19] == 6],
    vars,
    All
];

Check that we get the same number of instances:

Length @ bools

9

And a function to convert the booleans into p values:

toP[bools_] := Table[Boole[bools[[i]]] + 2 Boole[bools[[i+19]]], {i, 19}]

So, the following are the instances:

toP /@ bools //Column //TeXForm

$\begin{array}{l} \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,1,1\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,3\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,1,2\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,0,1\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,3\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,2,1\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,0,2\} \\ \{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2\} \\ \end{array}$