Re: generalized foldlist problem - part 2

*To*: mathgroup at smc.vnet.net*Subject*: [mg69269] Re: generalized foldlist problem - part 2*From*: "Arkadiusz Majka" <Arkadiusz.Majka at telekomunikacja.pl>*Date*: Mon, 4 Sep 2006 04:47:12 -0400 (EDT)*References*: <eddqb2$3tl$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

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

**Follow-Ups**:**Re: Re: generalized foldlist problem - part 2***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>

**Re: Why doesn't Mathematica solve this simple differential equation?**

**Re: Books on learning mathematics with Mathematica**

**Re: Re: Re: generalized foldlist problem - part 2**

**Re: Re: generalized foldlist problem - part 2**