Oof -- and of course it would take 1/6 the time if you say WLOG that A/B/C first appear in alphabetical order, then count each string with weight 1 or 3 or 6, depending on whether it mentions 1 or 2 or 3 of the sequences. --Michael On Fri, Jul 23, 2010 at 10:39 AM, Michael Kleber <michael.kleber@gmail.com>wrote:
Counts up through length 12 are:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267
It's not hard to do deterministically, in a computer algebra package. To check if a string like "ABCABA" is a feasible interleaving characteristic string, you just transform it into a set of linear inequalities constraining the six unknowns describing the three arithmetic progressions, and test whether there's a solution.
In addition to the obvious checks -- e.g. that the second term in the As progression is larger than the first of the Cs and smaller than the second of the Bs -- you need extra inequalities asserting that the last term mentioned in the string (here the third A) is smaller than each term that implicitly comes after the string (fourth A, third B, second C). And likewise for the terms that come before the string starts.
Something like Mma has no trouble finding an arbitrary point in the solution space for a set of linear equalities, or else proving that the set is empty. Code below, as long as you promise not to complain about poor style.
Of course you don't take all strings of length n; rather you first list all the strings of length n-1, and then append each of A,B,C to them and test the results.
The time to verify each candidate string goes up with n, of course -- you're adding inequalities, though only at a linear rate and still over a six-dimensional space, and you're also increasing the number of putative strings that need checking. The exhaustive enumeration up through length 12 took under 7 minutes.
--Michael
(* Number of ways to interleave N elements from 3 arithmetic seqs *)
(* Given a string like "ABCABA", produce a set of inequalities *) (* about the three arithmetic progressions giving successive A/B/Cs *) (* The Nth occurrence (1-indexed) of character X corresponds to the value *) (* BASE[X] + N * DELTA[X] *)
(* In all functions, seq is eg {"A", "B", "C", "A", "B", "A"} *)
(* The arithmetic-progression value of the ith element of seq *) value[seq_, i_] := BASE[seq[[i]]] + DELTA[seq[[i]]] * numoccur[seq,i] numoccur[seq_, i_] := Count[Take[seq,If[i>0,i,Length[seq]+i+1]],seq[[i]]]
(* First element of the seq is greater than anything that would precede it *) lowerbound[seq_] := (BASE[#] < value[seq,1])& /@ Union[seq] (* Each element of the seq is greater than the previous one *) upperbound[seq_] := (value[seq,-1] < value[Append[seq,#],-1])& /@ Union[seq] (* Last element of the seq is less than anything that would follow it *) ordering[seq_] := Table[ value[seq,i] < value[seq,i+1], {i,Length[seq]-1} ]
ineqs[seq_] := Join[ lowerbound[seq], ordering[seq], upperbound[seq] ] vars[seq_] := Join @@ ({BASE[#],DELTA[#]}& /@ Union[seq])
witness[seq_] := FindInstance[ ineqs[seq], vars[seq] ] witness[s_String] := witness[Characters[s]]
(* All obtainable length-n shuffles of three arithmetic seqs: *) names = {"A", "B", "C"}
shuf[0] := {""} candidates[n_] := Flatten[Table[ob<>ch, {ob,shuf[n-1]}, {ch, names}]] shuf[n_] := shuf[n] = Select[ candidates[n], witness[#] != {}& ]
--------- In[18]:= Table[Length[shuf[i]],{i,0,12}]
Out[18]= {1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267}
In[19]:= TimeUsed[]/60
Out[19]= 6.73642
On Fri, Jul 23, 2010 at 7:12 AM, Fred lunnon <fred.lunnon@gmail.com>wrote:
On 7/23/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values:
1, 3, 9, 27, 75, 189, 447, 951, 1911 ...
Value f_3(8) = 1911 further confirmed by 2-hour run of a million trials.
If the words are assumed to be uniformly distributed, the expected number of trials to find all X = f_m(n) should be about X log X, by a standard cigarette card / Pokemon token collecting argument. The program performance is substantially worse, because uniform distribution of AP's skews words away from those with long blocks of fewer than m symbols: the situation might be improved by skewing the AP's deliberately to counterbalance the effect, but it's a delicate business.
More satisfactory would be a viable deterministic algorithm! WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.