Re: generalized foldlist problem - part 2
- To: mathgroup at smc.vnet.net
- Subject: [mg69269] Re: generalized foldlist problem - part 2
- From: "Arkadiusz Majka" <Arkadiusz.Majka at telekomunikacja.pl>
- Date: Mon, 4 Sep 2006 04:47:12 -0400 (EDT)
- References: <eddqb2$3tl$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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
- Follow-Ups:
- Re: Re: generalized foldlist problem - part 2
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: Re: generalized foldlist problem - part 2