Here's an array-oriented approach.
The key idea is to convert the list of quantities to a running total, so
that each input and output is identified uniquely in the stream of results.
in =: 1000 2000 1500 1000
out =: 500 3000 1000
]ins =: 0 , +/\ in
0 1000 3000 4500 5500
]outs =: 0 , +/\ out
0 500 3500 4500
Now we can write a verb that takes an interval representing one output
and looks up in the list representing all the inputs, to find which
inputs correspond to that output:
NB. x is low#, high#, y is list of #s, result is table of
NB. (intvl in y), (amount allocated to intvl)
fifo1 =: ([: ((] ,. {~) I.@:*) 2 -~/\ {:@[ <. {...@[ >. ])"1
The <. and >. have the effect of excluding all the intervals that don't
apply, and then it's just a matter of converting the nonempty intervals
to the desired output format.
0 500 fifo1 ins
0 500
500 3500 fifo1 ins
0 500
1 2000
2 500
3500 4500 fifo1 ins
2 1000
To do all the calculations, just apply fifo1 on each interval of outputs:
NB. x is list of outputs, y is list of inputs
NB. Convert each to running total, then allocate each output
NB. among the correct inputs. Then, prepend the number of
NB. the output to give a table of
NB. output-intvl input-intvl amount
fifo =: [: ; i...@#@[ ,.&.> (2&(]\)@[ <@fifo1 ])&(0 , +/\)
out fifo in
0 0 500
1 0 500
1 1 2000
1 2 500
2 2 1000
WARNING!! This two-liner is not ready for production. It runs in time
O(*:n). But I think it would be easy to bring to O((*^.)n) by adding a
step where, after converting the lists to running sums, you use
(inputs I. outputs)
to reduce the number of inputs you have to examine for each output; then
run fifo1 on the reduced set and add the starting index back into the
result. Details left to the motivated.
Henry Rich
bill lam wrote:
> I want to calculate a fifo problems to match in-qty to out-qty,
>
> Assuming all qty are positive
> in-qty 1000 2000 1500 1000
> out-qty 500 3000 1000
> then a verb fifo, such that
>
> 500 3000 1000 fifo 1000 2000 1500 1000
>
> will give
>
> 0 0 500
> 1 0 500
> 1 1 2000
> 1 2 500
> 2 2 1000
>
> where format in each row,
> index-to-outqty index-to-inqty qty-allocated
>
> I have written a simple scalar C algorithm below and want to learn how to do
> it
> in vector J approach.
>
> fifo=: 4 : 0
> out=. x
> in=. y
> ox=. ix=. 0 [ z=. 0 3$0
> while. (ox<#out) *. ix<#in do.
> a=. ox{out
> b=. ix{in
> if. a=b do.
> z=. z, ox, ix, a
> out=. 0 ox}out
> in=. 0 ix}in
> ox=. >:ox [ ix=. >:ix
> elseif. a<b do.
> z=. z, ox, ix, a
> out=. 0 ox}out
> in=. (b-a) ix}in
> ox=. >:ox
> elseif. a>b do.
> z=. z, ox, ix, b
> out=. (a-b) ox}out
> in=. 0 ix}in
> ix=. >:ix
> end.
> end.
> z
> )
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
