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: [mg69282] Re: [mg69269] Re: generalized foldlist problem - part 2
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Tue, 5 Sep 2006 05:30:54 -0400 (EDT)
  • References: <eddqb2$3tl$1@smc.vnet.net> <200609040847.EAA23476@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

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: RE: Co-Displaying Combinatorica and Graphics Objects
  • Next by Date: Using FullSimplify to check hand algebra
  • Previous by thread: Re: generalized foldlist problem - part 2
  • Next by thread: RE: Re: generalized foldlist problem - part 2