MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
>>>>
>>


  • Prev by Date: Re: Simplify UnitStep expressions
  • Next by Date: RE: Re: Dot Product in Cylindrical Coordinates
  • Previous by thread: RE: Re: generalized foldlist problem - part 2
  • Next by thread: Re: generalized foldlist problem - part 2