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


  • Prev by Date: 2nd attempt at post with corrected code
  • Next by Date: Re: Problem with using /.
  • Previous by thread: Re: Re: generalized foldlist problem - part 2
  • Next by thread: Re: Re: generalized foldlist problem - part 2