RE: Re: generalized foldlist problem - part 2

*To*: mathgroup at smc.vnet.net*Subject*: [mg69298] RE: [mg69269] Re: generalized foldlist problem - part 2*From*: Majka Arkadiusz <Arkadiusz.Majka at telekomunikacja.pl>*Date*: Tue, 5 Sep 2006 05:31:29 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Andrzej! The very good new is that this is what I expected! Thank you very much. There is one , I hope small problem. Your program does not work for any list1. You can check List1={0.5,0.7,0.4} List2={2,2,4} GFMatrix is ok. But GF seems to drop in infinite loop - calculation doesn't finish. I made many tests and I find only one pattern: everything is ok. when elements of list1 are small. But I don't know how small - it looks like that a partial sum of their elements is not allowed to exceed 1 , but maybe I'm wrong. Any ideas? Arek -----Original Message----- From: Andrzej Kozlowski [mailto:akoz at mimuw.edu.pl] To: mathgroup at smc.vnet.net Subject: [mg69298] Re: [mg69269] Re: generalized foldlist problem - part 2 think I have corrected GF also, (sooner than I expected): GF[P_] := Module[{M = P}, Do[If[And @@ Thread[Total[ Take[M, s]] < 1], Continue[], M = NestWhile[ Join[(PadRight[#1, Length[#1] + 1] & ) /@ Take[#1, s - 1], (PadLeft[#1, Length[#1] + 1] & ) /@ Take[#1, s - 1 - Dimensions[#1][[1]]]] & , M, ! And @@ Thread[Total[#1[[All, Range[Length[ Flatten[Split[#1[[s]]] /. {l___, {(0) ..}} :> {l}]]]]]] < 1] & ]], {s, Dimensions[M][[1]]}]; M] It works at least in the case of your first example. Please test it and let me know if you find any problems. I really cannot spare have the time to do it myself. By the way, even if this is finally what you desire, I can see that the code could be made a more efficient. However, I think it is efficient enough, and as I wrote above I should not be spending too much time on this so I hope other people will look at this carefully or propose their own alternative code. Andrzej Kozlowski On 4 Sep 2006, at 20:09, Andrzej Kozlowski wrote: > O.K., I see. I think, GFMatrix needs only a slight correction: > > GFMatrix[list1_, > list2_] := > Transpose[DeleteCases[Transpose[Normal[SparseArray[Flatten[Table[If > [j <= > i + list2[[i]] - 1, {i, j} -> list1[[i]], {i, j} -> 0], { > i, Length[list2]}, {j, i, Total[list2] }], 1]]]], > {Repeated[0]}]] > > > I see the problem with GF too, but I have not got the time to > correct it right now, so I will probably send you corrected version > tomorrow. > > Andrzej > > > > > On 4 Sep 2006, at 16:39, Majka Arkadiusz wrote: > >> Yes, I read it. >> >> Take: >> >> List1={0.4,0.2,0.9} >> List2={8,1,7} >> >> What I want to mean: 0.4 appears 8 times, 0.2 - 1 time, 0.9 - >> seven times. >> And my matrix reads >> >> {{0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0},{0,0.2,0,0,0,0,0,0,0}, >> {0,0,0.9,0.9,0.9, >> 0.9,0.9,0.9,0.9}} >> >> Your solution is bounded to dim=3. Could you , please enlarge it ? >> >> Moreover, for your your solution which is >> >> 0.4 0.4 0.4 0 0 >> 0 0.2 0 0 0 >> 0 0 0.9 0.9 0.9 >> >> we apply GF >> >> and get >> >> 0.4 0.4 0.4 0 0 0 >> 0 0 0.2 0 0 0 >> 0 0 0 0.9 0.9 0.9 >> >> This is not what I want. >> >> I want you to >> >> 1) keep the first row - because all elements are <=1 >> 2) keep the the first two rows - because first row + second row is >> <=1 >> (suming along columns) >> 3) you can't keep first three rows (whole matrix in this example) >> because >> suming along the third column gives 1.3 what is >1. So I have to >> shift it on >> the right of one position and the third row appears to be >> >> 0 0 0 0 0.9 0.9 0.9 >> >> Now the solution is >> >> 0.4 0.4 0.4 0 0 >> 0 0.2 0 0 0 >> 0 0 0 0.9 0.9 0.9 >> >> Now its enough to fill right corner by zero's and Plus@@% >> >> >> Another example, how you procedures should work >> >> list1 = {0.8, 0.1, 0.2} >> list2 = {8, 3, 3} >> >> GFMatrix[list1, list2] gives >> >> 0.8 0.8 0.8 0.8 0.8 0.8 0.8 0.8 >> 0 0.1 0.1 0.1 0 0 0 0 >> 0 0 0.2 0.2 0.2 0 0 0 >> >> And GF[%] gives >> >> 0.8 0.8 0.8 0.8 0.8 0.8 0.8 0.8 >> 0 0.1 0.1 0.1 0 0 0 0 >> 0 0 0 0 0.2 0 0 0 >> >> One more example >> >> List1={0.8,0.3,0.9} >> List2={3,3,3} >> >> GF >> >> 0.8 0.8 0.8 0 0 >> 0 0 0 0.3 0.3 0.3 0 >> 0 0 0 0 0 0 0.9 0.9 0.9 >> >> One more >> >> List1={0.5,0.5,0.5} >> List2={3,3,3} >> >> GF >> >> 0.5 0.5 0.5 >> 0 0.5 0.5 0.5 >> 0 0 0 0.5 0.5 0.5 >> >> I hope its clear but I am ready to clarify as long as we get what >> I desire >> :) >> >> Arek >> >> -----Original Message----- >> From: Andrzej Kozlowski [mailto:akoz at mimuw.edu.pl] To: mathgroup at smc.vnet.net >> Subject: [mg69298] Re: [mg69269] Re: generalized foldlist problem - part 2 >> >> Hmm... Did you really have a look at the solutions I posted? Here >> are my two >> functions: >> >> GFMatrix[list1_, list2_] := Normal[SparseArray[Flatten[Table[If[j >> <= i + >> list2[[i]]*-1, {i, j} -> list1[[i]], {i, j} -> 0], {i, Length >> [list2]}, {j, >> i, Length[list1] + i - 1}], 1]]] >> >> GF[P_]:= Module[ { M=P}, Do[ M = NestWhile[ Join[ ( PadRight[ #1, >> Length[#1] >> + 1] & ) /@ Take[ #1, s], ( PadLeft[ #1, Length[#1] + 1] & ) /@ >> Take[ #1, s >> - Dimensions[#1][ [1]]]] & , M, ! And @@ Thread[ Total[ #1[ [ All, >> Range[ >> Length[ Flatten[ Split[ #1[ [s]]] /. { l___, { (0)..}} :> >> {l}]]]]]] < 1] & >> ], { s, Dimensions[M][ [1]]}]; M] >> >> Now, let's consider your example: >> >> list1 = Table[Random[], {10}]; >> list2 = Table[Random[Integer, {1, 5}], {10}] >> >> Here is the solution: >> >> In[32]:= >> m=GFMatrix[list1,list2]; >> >> In[31]:= >> Total[GF[m]]//Timing >> >> Out[31]= >> {0.015873 Second, >> {0.518177,0.518177,0.518177,0.518177,0.548916,0.588317, >> >> 0.588317,0.588317,0.997371,0.997371,0.997371,0.997371,0.997371,0.5346 >> 07, >> >> 0.534607,0.534607,0.534607,0.78564,0.251032,0.251032,0.535924,0.53592 >> 4, >> >> 0.284892,0.284892,0.412818,0.127926,0.127926,0.127926,0.818314,0.6903 >> 88, >> 0.690388,0.690388,0.690388,0.776409,0,0,0,0,0,0,0,0,0}} >> >> This is pretty fast, and I think satisfies your requirements. By >> contrast, >> your own solution does not work at all on my machine, producing >> just a bunch >> of error messages. Perhaps the solution is in some way not what >> you wanted, >> but then it would be helpful if you could point out what is wrong >> with it. >> >> Andrzej Kozlowski >> >> >> >> >> >> On 4 Sep 2006, at 09:47, Arkadiusz Majka wrote: >> >>> Thanks for all answers. Andrzej presented "full solution" - and >>> he is >>> right - that's what I wanted to get. (Of course, I didn't take me a >>> lot of time to get it from Jens or others answers) >>> >>> In the code below you will see what I want to do next with our >>> matrix >>> - it is explained below. >>> >>> So lets take >>> >>> list1=Table[Random[],{10}]; >>> list2=Table[Random[Integer,{1,5}],{10}] >>> >>> lets use Anrzeje's solution >>> >>> ma=GFMatrix[list1,list2] >>> >>> and now my code that manipulates ma in the way explained below >>> (it is >>> not allowed that Plus@@ma[[i]] is >1 for every i. ) >>> >>> The code is the following >>> >>> moje[T_] := Module[{i, matrix, dl, ile, ile1, ile22, ile33}, >>> dl[i_] := First[Flatten[Position[Plus @@ Take[matrix[i], i + >>> 2], _?(# > 1 &)]] /. {} -> {0}]; >>> matrixNew[i_] := ReplacePart[matrix[i], matrix[ >>> i][[i + 2]] /. {0 -> list1[[i + 2]]}, i + 2]; >>> ile2[i_] := If[dl[i] > 0, Last[Flatten[Position[Plus @@ Take[ >>> matrixNew[i], i + 2], _?(# > 1 &)]] /. {} -> {0}], 0]; >>> ile33[i_] := ile2[i] - dl[i] + If[dl[i] > 0, 1, 0]; >>> matrix[0_] := ma; >>> matrix[i_] := matrix[i] = Flatten[Join[{Map[PadRight[#, >>> Dimensions[Map[PadRight[#, >>> Length[#] + ile33[i - 1], 0, >>> ile33[i - 1]] &, Drop[matrix[i - 1], i]]][[2]]] &, Take[ >>> matrix[i - 1], i]], Map[PadRight[#, Length[#] + >>> ile33[i - >>> 1], 0, ile33[i - 1]] &, Drop[matrix[i - 1], >>> i]]}], 1]; >>> matrix[T]] >>> >>> and solution >>> >>> moje[Length[list1] - 1] >>> >>> This algorithm is very brutal and very time consuming. Program >>> repeats >>> calculations etc. Do you have any ideas how to improve it or rebuild >>> it entirely? >>> >>> p.s. I made many tests using my code and it is correct, i.e it >>> generates "solutions" that i expect. >>> >>> p.s2. The algorithm tries to simulate agents (say computing jobs) >>> that >>> arrive to a service (say computing element). "Power" of a service is >>> <= one. "Power" of agents <=1 - so sometimes more than one agent can >>> occupy a service , but their sum must by <= 1. Agents come in to a >>> service following the rule FCFS (first come first serve) - it means >>> tha tall agents must patiently waiting in the queue before >>> execution. >>> >>> Have a beautiful week, >>> >>> Arek >>> >>> >>> >>> Andrzej Kozlowski napisal(a): >>>> On 1 Sep 2006, at 23:41, Andrzej Kozlowski wrote: >>>> >>>>> >>>>> On 1 Sep 2006, at 11:41, Andrzej Kozlowski wrote: >>>>> >>>>>> >>>>>> On 31 Aug 2006, at 09:38, Arkadiusz Majka wrote: >>>>>> >>>>>>> Dear All, >>>>>>> >>>>>>> Thank all of you for your help regarding my "generalized fold >>>>>>> list >>>>>>> problem", that sounds >>>>>>> >>>>>>>>> I have two list >>>>>>>> >>>>>>>> list1=={a,b,c,d,e} >>>>>>>> list2=={3,2,5,1,6} >>>>>>>> >>>>>>>> and I want to apply a modified version of FoldList to list1 in >>>>>>>> the following way: list2 indicates that element a appears >>>>>>>> only 3 >>>>>>>> times (if space enough) beginning from the beginning of the >>>>>>>> list >>>>>>>> , element b appears 2 times, c - 5 times , etc. >>>>>>>> >>>>>>>> So the output should be >>>>>>>> >>>>>>>> GeneralizedFoldList[list1,list2]=={a,a+b,a+b+c,c+d,c+e} >>>>>>>> >>>>>>>> >>>>>>> >>>>>>> Now, I still need your help. What I want to do now, and what I >>>>>>> have >>>>>>> problem with, is to add a constraint to the algorithm, i.e every >>>>>>> element in my GeneralizedFoldList must be less than one. >>>>>>> The following example says what to do if it is not. >>>>>>> >>>>>>> Lets take two lists >>>>>>> >>>>>>> list1=={0.9,0.8,0.7} >>>>>>> list2=={3,3,3} >>>>>>> >>>>>>> All your algorithms use PadRight (you pad 0's). So the following >>>>>>> matrix >>>>>>> is built >>>>>>> >>>>>>> {{0.9, 0.9, 0.9, 0, 0}, {0, 0.8, 0.8, 0.8, 0}, {0, 0, 0.7, 0.7, >>>>>>> 0.7}} >>>>>>> >>>>>>> and we add elements along colums and obtain {0.9, 1.7, 2.4, 1.5, >>>>>>> 0.7} >>>>>>> >>>>>>> The first element is less than 1 so it's ok. The second is > 1 >>>>>>> what I >>>>>>> need to avoid. I want to avoid it by shifting the nonzero >>>>>>> elements of >>>>>>> the second and third row of above matrix of two positions: >>>>>>> {0,0,0,0.8,0.8,0.8,0}, {0,0,0,0,0.7,0.7,0.7}. >>>>>>> >>>>>>> I go on with suming along columns and discover that >>>>>>> everything is >>>>>>> fine >>>>>>> until I have to add 0.8 and 0.7 what is >1. So I repeat the >>>>>>> procedure >>>>>>> by shfting hte third row of the number of position that is >>>>>>> needed to >>>>>>> ensure that my sum is <1. >>>>>>> >>>>>>> Finally I obtain {{0.9, 0.9, 0.9, 0, 0, 0, 0, 0, >>>>>>> 0},{0,0,0,0.8,0.8,0.8,0,0,0},{0,0,0,0,0,0,0.7,0.7,0.7}} >>>>>>> and Plus@@% is what I desire. >>>>>>> >>>>>>> Thanks in advance! I hope you will manage :) >>>>>>> >>>>>>> Arek >>>>>>> >>>>>> >>>>>> >>>>>> Here is a (not very pretty) code that should do what you want >>>>>> starting with a matrix of the above kind: >>>>>> >>>>>> >>>>>> GF[P_]:==Module[{M==P},Do[M == NestWhile[ >>>>>> Join[(PadRight[#1, Length[#1] + 1] & ) /@ >>>>>> Take[#1, s], (PadLeft[#1, Length[#1] + 1] & ) /@ >>>>>> Take[#1, s - Dimensions[#1][[1]]]] & , M, >>>>>> !And @@ Thread[Total[#1[[All,Range[Length[ >>>>>> Flatten[Split[#1[[s]]] /. {l___, >>>>>> {(0)..}} :> {l}]]]]]] < 1] & ], >>>>>> {s, Dimensions[M][[1]]}]; M] >>>>>> >>>>>> >>>>>> Let's verify that it works. First, starting with your original >>>>>> case: >>>>>> >>>>>> >>>>>> In[8]:== >>>>>> M=={{0.9,0.9,0.9,0,0},{0,0.8,0.8,0.8,0},{0,0,0.7,0.7,0.7}}; >>>>>> >>>>>> >>>>>> In[9]:== >>>>>> GF[M]//InputForm >>>>>> >>>>>> Out[9]//InputForm== >>>>>> {{0.9, 0.9, 0.9, 0, 0, 0, 0, 0, 0}, >>>>>> {0, 0, 0, 0.8, 0.8, 0.8, 0, 0, 0}, >>>>>> {0, 0, 0, 0, 0, 0, 0.7, 0.7, 0.7}} >>>>>> >>>>>> Now let's change M somewhat: >>>>>> >>>>>> In[10]:== >>>>>> M=={{0.9,0.9,0.1,0,0},{0,0.1,0.8,0.3,0},{0,0,0.7,0.9,0.7}}; >>>>>> >>>>>> >>>>>> In[11]:== >>>>>> GF[M]//InputForm >>>>>> >>>>>> Out[11]//InputForm== >>>>>> {{0.9, 0.9, 0.1, 0, 0, 0, 0, 0}, {0, 0, 0.1, 0.8, 0.3, 0, >>>>>> 0, 0}, {0, 0, 0, 0, 0, 0.7, 0.9, 0.7}} >>>>>> >>>>>> So you only need to combine this with your favourite code from >>>>>> part 1. >>>>>> >>>>>> (PS. In answering part 1 I obviously misunderstood your >>>>>> question, but >>>>>> I think that was mainly because I do not think your function >>>>>> is in >>>>>> any way a "generalisation of Fold", or even of Fold >>>>>> [Plus,element,list]. As far as I can see it does not really >>>>>> perform >>>>>> any kind of "folding". >>>>>> >>>>>> Andrzej Kozlowski >>>>>> >>>>> >>>>> >>>>> In fact I still do not fully understand your original question >>>>> and, >>>>> in particular, if the example you originally posted (and which, if >>>>> any, of the solutions various people provided) were correct. >>>>> Just in >>>>> case, here is a "solution" to your original question, which I >>>>> think >>>>> is different from any of the ones I have seen: >>>>> >>>>> GFMatrix[list1_, >>>>> list2_] :== Normal[SparseArray[Flatten[Table[If[j =B2 i + >>>>> list2 >>>>> [[i]] - 1, >>>>> Rule[{i, j}, list1[[i]]], Rule[{i, >>>>> j}, 0]], {i, Length[list2]}, {j, i, Length[list1] + >>>>> i - >>>>> 1}], 1]]] >>>>> >>>>> GFMatrix builds the matrix, which, I think, you need in the second >>>>> part of the question. The code makes no use of PadLeft or >>>>> PadRight. >>>>> However, note that in your original example, the output is not the >>>>> same as you gave as the correct one, although the output below >>>>> seems >>>>> to me to fit better your verbal description of what you wanted >>>>> done: >>>>> >>>>> >>>>> list1=={a,b,c,d,e}; >>>>> list2=={3,2,5,1,6}; >>>>> >>>>> >>>>> GFMatrix[list1,list2] >>>>> >>>>> >>>>> {{a, a, a, 0, 0, 0, 0, 0, 0}, >>>>> {0, b, b, 0, 0, 0, 0, 0, >>>>> 0}, {0, 0, c, c, c, c, c, >>>>> 0, 0}, {0, 0, 0, d, 0, 0, >>>>> 0, 0, 0}, {0, 0, 0, 0, e, >>>>> e, e, e, e}} >>>>> >>>>> >>>>> Total[%] >>>>> >>>>> >>>>> {a,a+b,a+b+c,c+d,c+e,c+e,c+e,e,e} >>>>> >>>>> This is longer than the output you gave as the right solution, >>>>> which >>>>> was only a part of the above, namely {a,a+b,a+b+c,c+d,c+e}. >>>>> >>>>> Andrzej Kozlowski >>>>> >>>>> >>>> >>>> Oops, the code I copied and pasted in did not come out the way it >>>> should have done. It shoudlhave been: >>>> >>>> GFMatrix[list1_, list2_] := Normal[SparseArray[Flatten[Table[If >>>> [j <= >>>> i + list2[[i]] - 1, {i, j} -> list1[[i]], {i, j} -> 0], {i, Length >>>> [list2]}, {j, i, Length[list1] + i - 1}], 1]]] >>>> >>>> Andrzej Kozlowski >>> >