Re: Re: generalized foldlist problem - part 2
- To: mathgroup at smc.vnet.net
- Subject: [mg69286] Re: [mg69269] Re: generalized foldlist problem - part 2
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 5 Sep 2006 05:31:05 -0400 (EDT)
- References: <7BEBBEE71B48844B82F6D39CC9A3ABF0015189B0@OCE1B045>
- Sender: owner-wri-mathgroup at wolfram.com
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: [mg69286] 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.53460
> 7,
>
> 0.534607,0.534607,0.534607,0.78564,0.251032,0.251032,0.535924,0.535924
> ,
>
> 0.284892,0.284892,0.412818,0.127926,0.127926,0.127926,0.818314,0.69038
> 8,
> 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
>>