Re: Re: generalized foldlist problem - part 2
- To: mathgroup at smc.vnet.net
- Subject: [mg69299] Re: [mg69269] Re: generalized foldlist problem - part 2
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 6 Sep 2006 04:28:08 -0400 (EDT)
- References: <7BEBBEE71B48844B82F6D39CC9A3ABF00153C2DE@OCE1B045>
- Sender: owner-wri-mathgroup at wolfram.com
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: [mg69299] Re: [mg69269] 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: [mg69299] 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.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 >>>> >>