dimarts, 18 de març del 2008

Wheel problem

I was thinking about maps, zips, and other "functions to list" operations, and I though, "Is there any way to combine one list with itself using a wheel procedure". Lets assume we have one unknown size list and a function that receives 2 parameters and returns one (for example an addition of 2 numbers), and we want to combine 1rst element with 2ond, 2ond with 3rd and so on until the last element is combined with the first one again.
Here there is an example
List = [1,2,3] f = function(a,b)
R:=[f(3,1),f(1,2),f(2,3)];

I thought it was really easy to solve it by multiple ways using a complexity of 2*n. For example first counting list size (Complexity n) and then combine elements (Complexity n). But then I thought how this complexity could be reduced. Moreover I realized I was doing this procedure by hand just with Complexity n so it could be possible to implement it. Then I thought this solution

function wheel2(L,f,&last)
if (L.tail eq []) then
last:=L.head;
return [];
else
return Append(wheel2(L.tail,f,last), f(L.head,L.tail.head));
end if;
end function;

function wheel(L,f);
return Append(wheel2(L,f,last), f(last,L.head));
end function;

I didn't find any way to solve the "last" parameter, but I will think about it. If anyone think there is a better solution feel free to post it, I will be really pleased to comment different solutions.