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
>
>