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