Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: When Wolfram's technical support cannot help

• To: mathgroup at smc.vnet.net
• Subject: [mg105261] Re: [mg105255] When Wolfram's technical support cannot help
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Wed, 25 Nov 2009 22:59:19 -0500 (EST)
• References: <200911251114.GAA13425@smc.vnet.net>

Ant King wrote:
> Hi
> 
> I sent this email to technical support (as I hold a premier licence)
> 
> I am looking for a single function that will extract the cyclic part of (a)
> a completely cyclic sequence and (b) an eventually cyclic sequence. So if
> 
> data1={1,2,3,1,2,3,1,2,3,1,2,3} then cyclicpart[data1] should return {1,2,3}
> 
> And if
> 
> data2={5,9,11,8,1,2,3,1,2,3,1,2,3,1,2,3} then cyclicpart[data2] should also
> return {1,2,3}
> 
> And this was the reply that I got
> 
> Here is one way to extract out the cyclic part:
> 
> lis = Flatten[Join[Table[{1, 2, 3}, {8}]]]
> 
> p = Position[Table[BitXor[lis, RotateLeft[lis, i]], {i, 1, 10}],
>     ConstantArray[0, Length[lis]]][[1]] /. {a_} -> a
> lis[[1 ;; p]]
> 
> The above however will only work for case where the list always contains
> the repeated pattern.
> 
> There is no built-in function as such that will extract out the pattern
> automatically. I have filed a suggestion with our developers and you will
> be notified when this suggestion gets implemented. Again, my apologies for
> the delay and my thanks for your patience.
> 
> Now I don't believe that. I think that it should be quite achievable. Anyone
> got any ideas
> 
> Thanks a lot
> 
> Ant

You do not specify clearly what it is you want, or how the code somebody 
took time and effort to write fails to do what you want. So the readers 
need to fill in the details.

I'll take some guesses. You want a function that finds an ending 
repeated pattern, regardless of whether it is or is not preceded by a 
prior pattern. The final pattern must repeat at least twice. In a list 
such as
ll1 = {b,a,b,a,b}
the result should be {a,b}. In
ll2 = {a,b,a,b,a,b,b,a,b,a,b}
it should be {b,a,b,a,b} rather than {a,b}. In
ll3 = {b,a,b,a,b,a,b,b,a,b,a,b,a,b}
it should be {b,a,b,a,b,a,b} rather than {a,b}, because that is a longer 
suffix. Or should it be {a,b} because that repeats more times? I will 
guess the former.
What about
ll4 = {b,a,b,b,a,b,b,a,b,b,a,b}
Should it be {b,a,b,b,a,b} (repeats twice), or {b,a,b} (repeats four 
times)? This is an underspecified problem. I'm going with the longer 
list. Can be altered by a recursive call plus a length check.

So here is one approach. I will not be surprised if there are better 
ways, using built-in pattern matching (or related) capabilities.

longestRepeat[ll_List] := Module[
   {len=Length[ll], n=1, max=0},
   While [n<=len/2,
	If [ll[[len-n+1;;len]] ===
	  ll[[len-2*n+1;;len-n]], max=n];
	n++];
   ll[[len-max+1;;len]]
   ]

The examples:

In[59]:= longestRepeat[ll1]
Out[59]= {a, b}

In[60]:= longestRepeat[ll2]
Out[60]= {b, a, b, a, b}

In[61]:= longestRepeat[ll3]
Out[61]= {b, a, b, a, b, a, b}

In[62]:= longestRepeat[ll4]
Out[62]= {b, a, b, b, a, b}

In[63]:= data2={5,9,11,8,1,2,3,1,2,3,1,2,3,1,2,3}
Out[63]= {5, 9, 11, 8, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3}

In[64]:= longestRepeat[data2]
Out[64]= {1, 2, 3, 1, 2, 3}

Daniel Lichtblau
Wolfram Research

• References:
  • When Wolfram's technical support cannot help
    • From: "Ant King" <mathstutoring@ntlworld.com>