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: [mg69283] RE: [mg69269] Re: generalized foldlist problem - part 2
  • From: Majka Arkadiusz <Arkadiusz.Majka at telekomunikacja.pl>
  • Date: Tue, 5 Sep 2006 05:30:56 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

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: [mg69283] 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.534607,
      
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.690388,
     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: Why doesn't Mathematica solve this simple differential equation?
  • Next by Date: Re: Re: generalized foldlist problem - part 2
  • Previous by thread: Re: Re: generalized foldlist problem - part 2
  • Next by thread: Re: Re: generalized foldlist problem - part 2