# Generating a variable size table one element at a time

I can produce a variable size list of strings like AACBBAABC with this code:

test[n_] :=
Flatten[ Table[ StringJoin @@ Table[ Subscript[\[Zeta], i], {i, 1, n}], ##] & @@
Table[{ Subscript[\[Zeta], i], {"A", "B", "C"}}, {i, 1, n}], n - 1]


My problem is that ultimately n will be such that the table has $10^{17}$ elements.
What I want to do is generating the elements one at a time so that I can run a test on the string to validate it. The number of good strings will be $<<10^{17}$. In essence I need a code that will have a variable number of loops depending on n. My $70$ year old brain is having a problem coming up with an answer!

• $10^{17}$ elements??? At 1 byte per element, that's about 100 peta bytes! Do you work for the NSA or Google? :D
– rm -rf
Commented Nov 27, 2013 at 20:39
• If you could check a billion elements per second (a rate of 1 GHz), it would take approximately π years. You might want to figure out how to skip large chunks of elements. Commented Nov 27, 2013 at 21:01
• Your test function looks too complex. Why don't you use something simple and fast like test[n_] := StringJoin @@@ Tuples[{"A", "B", "C"}, {n}] Commented Nov 27, 2013 at 21:11
• test[n] equivalent to Tuples[{"A","B","C"},n]. What is it that you want to know about all tuples of this triplet? Perhaps you want to know how many there are? If so, this can be much more easily found that listing them all. BTW, what constitutes a good string? Commented Nov 27, 2013 at 21:14
• If you are working with DNA sequences have you seen the functionality in the Biomolecular Sequences guide? Commented Jun 19, 2023 at 11:55

I'm interpreting the goal to be to iterate through all possible strings consisting of the three characters "A", "B", and "C" up to some stringlength.

We note that there's a correspondence between each such string and the integers written in base 3. We can map to digits thus: "A"->0, "B"->1, "C"->2. Using integers might make iteration easier. Unfortunately, this correspondence isn't one-to-one, because "A", "AA", "AAA", etc all map to 0. Our iteration would need to visit each integer multiple times in order to hit each 0-padded representation.

If we add some special-casing, we can get integers to do the bulk of the work.

NextDigitSequence3[seq_] := ConstantArray[0, 1 + Length@seq] /; AllTrue[seq, EqualTo[2]];
NextDigitSequence3[seq_] := IntegerDigits[1 + FromDigits[seq, 3], 3, Length@seq]


Try it out:

NestList[NextDigitSequence[3], {}, 13]
(* {{}, {0}, {1}, {2}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}, {0, 0, 0}} *)


Now, if the test can be reformulated as a test against digit sequences rather than strings, we could do something like this:

TheChecker[seq_] := {0} == Commonest[seq]; (* <-- just an example test *)
Select[NestList[NextDigitSequence3, {}, 40], TheChecker]
(* {{0}, {0, 0}, {0, 0, 0}, {0, 0, 1}, {0, 0, 2}, {0, 1, 0}, {0, 2, 0}, {1, 0, 0}, {2, 0, 0}, {0, 0, 0, 0}} *)


Of course, with a large number of strings/digit-sequences to check, we don't want to generate the list first. We could instead use Sow/Reap.

current = {};
Reap[
Do[
If[TheChecker[current], Sow[current]];
current = NextDigitSequence3[current],
40]]


If you don't want to actually collect the validated strings/digit-sequences, then you could still use the Do loop, but just handle the elements differently.

If the test cannot be reformulated, and must be done on strings, then we'll need to translate between digit-sequences and strings, but that's easy by just replacing 0->"A", 1->"B", 2->"C" and joining. This can be done either in TheChecker directly or as a helper function.

If this will need to be generalized to different numbers of generating characters, we could use a slightly different approach:

NextDigitSequence[order_][seq_] :=
ConstantArray[0, 1 + Length@seq] /; AllTrue[seq, EqualTo[order - 1]];
NextDigitSequence[order_][seq_] :=
IntegerDigits[1 + FromDigits[seq, order], order, Length@seq]


So, NextDigitSequence3 is NextDigitSequence[3].

Caveat: This took several seconds to check the first million digit-sequences. The pattern matching requires a check each time--maybe there's a more elegant iteration mechanism. Translating back and forth between strings and digits would add more time, obviously. So, I don't know how this reasonably gets you to the scale you're talking about. You could iterate through swaths of cases in chunks, or just let it run until you got sick of waiting, or gather the results in some other way so you can see intermediate results as you go along.