Thanks Richard, Xiang and Eric for your suggestions!
-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:42 PM, reyssat <eric.reyssat at math.unicaen.fr> wrote:
> 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
>>
>
>