Hello,
I think the problem depends on wether you need a simple algorithm or an
efficient one for long strings.
The cyclic longest subsequence problem for 2 strings of length s seems
to be tractable in O(s^2) (or maybe O(s^2/log(s))).
The link http://hal.archives-ouvertes.fr/docs/00/10/91/96/PDF/D242.PDF
might be a starting point for more information and references.
Eric Reyssat
Paulo Grahl a ?crit :
> thanks a lot.
> A maxima version of the algorithm would be
>
> longerone(L1,L2):= if length(L1) > length(L2) then L1 else L2$
> lcs(L1,L2):= if (length(L1)=0) or (length(L2)=0) then []
> else if last(L1)=last(L2) then
> append(lcs(rest(L1,-1),rest(L2,-1)),makelist(last(L1),i,1,1))
> else longerone(lcs(rest(L1,-1),L2),lcs(L1,rest(L2,-1)))$
>
> but it still does not work for my goal as I need to check within
> "circular" lists, i.e,
> [a,a,b,c,d] is equivalent to [a,b,c,d,a] and so on and the algorithm
> proposed gives different results depending on which one of the
> equivalent lists I am using.
>
> for example applying it to [a,a,b,c] and [a,b,z,a] I find [a,b] as the
> longest common sequence, but I need [a,a,b]. I can apply the algorithm
> several times with one of the sequences cycled and get the longest
> result, but I was wondering whether a simpler way to do it exists.
> Thanks.
>
> --Paulo
>
> Paulo Gustavo Grahl, CFA
> ------------------------------------------
> pgrahl at gmail.com
> pgrahl at fgvmail.br
> +55(21) 8809-9254
> www.linkedin.com/in/pgrahl
> ------------------------------------------
>
>
>
>
> On Wed, Mar 4, 2009 at 2:58 AM, Xiang Liu <hsiang.liu at gmail.com> wrote:
>
>> I have no idea on Maxima's approach. But your problem is a typical longest
>> common sequence in Algorithm.
>>
>> We write A=A[1:n], B=B[1:m]. Now,
>>
>> if A[n]=B[n] then
>> result=common(A[1,n-1],B[1,n-1]).append(A[n]);
>> else
>> result=longerOne( common(A[1,n-1], B[1,n]), common(A[1,n], B[1,n-1]) );
>>
>> The pseudo code above is just a skeleton.
>>
>> On Wed, Mar 4, 2009 at 12:10 AM, Paulo Grahl <pgrahl at gmail.com> wrote:
>>
>>> Dear list members:
>>>
>>> I'm facing the following problem:
>>> given a two lists, for example, [a,b,c,x,a] and [z,a,a,b]
>>> I'm interested in finding the largest sequence of symbols that match
>>> both lists, considering lists as circular, i.e.,
>>> [z,a,a,b]=[a,a,b,z]=[a,b,z,a]=[b,z,a,a].
>>> In the above example, the sequence "a,b" appears in both lists, but I
>>> would be interested in finding the sequence "a,a,b" which is the
>>> longest one to appear in both lists (considering the lists as
>>> circular).
>>>
>>> Any idea on how to find such common patterns ?
>>> Thanks.
>>> Paulo
>>>
>>>
>>> Paulo Gustavo Grahl, CFA
>>> ------------------------------------------
>>> pgrahl at gmail.com
>>> pgrahl at fgvmail.br
>>> +55(21) 8809-9254
>>> www.linkedin.com/in/pgrahl
>>> ------------------------------------------
>>> _______________________________________________
>>> Maxima mailing list
>>> Maxima at math.utexas.edu
>>> http://www.math.utexas.edu/mailman/listinfo/maxima
>>>
>>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>