Re: generalized foldlist problem - part 2

*To*: mathgroup at smc.vnet.net*Subject*: [mg69422] Re: generalized foldlist problem - part 2*From*: Arkadiusz.Majka at gmail.com*Date*: Tue, 12 Sep 2006 06:52:30 -0400 (EDT)*References*: <7BEBBEE71B48844B82F6D39CC9A3ABF00153C2DE@OCE1B045> <edm0pm$cgf$1@smc.vnet.net>

Andrzej, Apologies po replying so late. Everything is ok - your code is correct, I have not found other bugs. It is also ten times faster than mine.... :) Thank you very much, Arek Andrzej Kozlowski napisal(a): > Indeed, there was another bug. The new code is: > > 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[ [ Range[s], Range[ Length[ > Flatten[ Split[ #1[ [s]]] /. { l___, > { (0)..}} :> {l}]]]]]] < 1] & ]], > { s, Dimensions[M][ [1]]}]; M] > > > It works in your example: > > list1= { 0.5,0.7,0.4}; > list2= { 2,2,4}; > p = GFMatrix[list1, list2] > {{0.5, 0.5, 0, 0, 0, 0}, {0, 0.7, 0.7, 0, 0, 0}, {0, 0, 0.4, 0.4, > 0.4, 0.4}} > GF[p] > {{0.5, 0.5, 0, 0, 0, 0, 0, 0}, {0, 0, 0.7, 0.7, 0, 0, 0, 0}, {0, 0, > 0, 0, 0.4, 0.4, 0.4, 0.4}} > Total[%] > {0.5, 0.5, 0.7, 0.7, 0.4, 0.4, 0.4, 0.4} > > Please test it and let me know if you find any other bugs. > > Andrzej Kozlowski > > > On 5 Sep 2006, at 10:05, Majka Arkadiusz wrote: > > > 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: [mg69422] Re: Re: generalized foldlist problem - part 2 > > > > (tm) Pro* I > > 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: [mg69422] Re: 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.534 > >>> 6 > >>> 07, > >>> > >>> 0.534607,0.534607,0.534607,0.78564,0.251032,0.251032,0.535924,0.5359 > >>> 2 > >>> 4, > >>> > >>> 0.284892,0.284892,0.412818,0.127926,0.127926,0.127926,0.818314,0.690 > >>> 3 > >>> 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 > >>>> > >>