[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1087.0. "Algorithm for incrementing lists.." by SLDA5::DUNAISKY (Freedom isn't free.) Fri May 26 1989 20:18

This is for a Digital project...

We need an algorithm to increment the numbers in a list of numbers (for
example, {1,2,3} a list of 3 numbers).  The algorithm would only increment one
number at a time, then a function would be run to compute a result based on the
numbers.

The result will be one of three values, LO, MED, AND HI.  (The function assures
that any increases in the numbers can only result in higher return values. 
i.e., if {1,1,1} is MED, then {1,2,1} can only be MED or HI, not LO.)

The object of the algorithm would be to detect all *maximized* cases (numbers
in the lists) where the result changes from one value to the next (i.e., from
LO to MED, from LO to HI, or from MED to HI.  Cases of the first two would be
"lo limits" and of the latter would be "med limits".)

Here's an example using a 3 number list:

	(1 1 1)		returns: LO
	(2 1 1)		returns: MED
	(1 2 1)		returns: LO
	(1 3 1) 	returns: HI
	(1 2 2)		returns: LO
	(1 2 3)		returns: LO
	(1 2 4)		returns: MED
 ---> Hence, we have found ONE case of a "lo limit": (1 2 3).  We still need 
	to try 	(1 1 4), etc., and also look for "med limits".

I've got a start on an algorithm (in LISP), but would like to validate it and
see if there is any actual theory behind this...

Any help (MAIL or notes reply) would be greatly appreciated.  Thanks,
Jonathan
T.RTitleUserPersonal
Name
DateLines
1087.1ALIEN::POSTPISCHILAlways mount a scratch monkey.Wed May 31 1989 11:4712
    Re .0:
    
    There can be infinitely many limits, such as one z for each possible x
    and y in (x y z).  It would help to know more about the function -- do
    we know anything about what properties it has?
    
    Also note that (2 2 2) might be a low limit if you change the third
    number but not if you change the first or second.  Should your
    algorithm present that information? 
    
    
    				-- edp
1087.2AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoWed May 31 1989 13:483
	I'm curious what application this is for.

	Dan
1087.3Not only that,POOL::HALLYBThe Smart Money was on GoliathWed May 31 1989 14:231
    I would be interested in a second explanation of the problem.
1087.4SLDA5::DUNAISKYFreedom isn't free.Fri Jun 02 1989 04:3041
Thanks for the replies so far.  Sorry if this is sounding a bit sketchy, i'll
try to fill in more details [a bit at a time].

re .1:

>    There can be infinitely many limits, such as one z for each possible x
>    and y in (x y z).  It would help to know more about the function -- do
>    we know anything about what properties it has?

For now, we can assume that the function will change value over a "reasonable"
period... (i think the algorithm may have to account for a function which
doesn't meet this assumption, but that's an exception that we probably don't
need to discuss here.)
    
>    Also note that (2 2 2) might be a low limit if you change the third
>    number but not if you change the first or second.  Should your
>    algorithm present that information? 

No;  that is what was meant by "maximized cases"... the low/med-limits should
only consist of lists with elements that are at their "highest" limit (doubt
that makes any more sense!)...

re .2:
>	I'm curious what application this is for.

System Level Design Analysis is the name of the group/project/application.
actually this is an "experiment" within that project: in brief (since i'm
trying to keep this topic focused on the algorythmic problem) we're going
to take 100's of computer system configurations, all of the "link paths"
within the configurations, and analyze them for bus utilization (the
"function" is based on emperical results)...  anyway, the real job is
presenting and using it, but we've got to get past a few hurdles (like this
one)!

re .3: >    I would be interested in a second explanation of the problem.

i hope you're at least 1/2 joking!   (i was thinking of extracting .0 and
using that as the documentation to the algorithm i have!... ;-)

thanks again,
jonathan
1087.5What is (244, 11, 1099)?POOL::HALLYBThe Smart Money was on GoliathFri Jun 02 1989 17:1414
> re .3: >    I would be interested in a second explanation of the problem.
> 
> i hope you're at least 1/2 joking!   (i was thinking of extracting .0 and
> using that as the documentation to the algorithm i have!... ;-)
    
    I'm dead serious, but you can blame me for being thick-headed if you
    like.  (There are times when I feel that way about others in this file).
    
    Exactly what "rule" is followed to determine if (a b c) or for
    that matter (a b c d e f g) is LO, MED or HI?  Or, to ask it yet
    another way, if the outputs are one of {LO, MED, HI}, what are
    the input(s) and how are they processed to produce the outputs?
    
      John
1087.6AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoFri Jun 02 1989 20:1611
     The function that maps (244,11,1099) into one of {LO, MED,
     HI} is given to you.  You don't need to know any more about
     it, other than x <= x', y <= y', z <= z' implies that
     f(x,y,z) <= f(x',y',z'), where results are ordered LO <= MED
     <= HI.
     
     The problem is to specify an algorithm that can take any
     such function and find the maximal whatever_he_called_them_-
     in_.0's.
     
     Dan
1087.7Thanks for the expoPOOL::HALLYBThe Smart Money was on GoliathFri Jun 02 1989 20:517
>     The function that maps (244,11,1099) into one of {LO, MED,
>     HI} is given to you.  
    
    More to the point, it ISN'T given to you.  Nor does it depend on when
    it is fed its inputs.  Two points that weren't clear to me.
    
      John
1087.8think processHERON::BUCHANANAndrew @vbo DTN 828-5805Sat Jun 03 1989 10:4249
	My understanding of the problem is as follows.

	Let P* be the set of lists of strictly positive integers.   Let
Q be a fixed, finite totally ordered set (in this case {LO,MED,HI}).
Let M be the set of monotonic functions from P* to Q, ie. functions, f, from
P* to Q which satisfy for all positive integers, I,p_1,...p_I,p'_1,...p'_I:

	(for all i = 1...I, p_i =< p'_i)  implies
	f(p_1, ..., p_I) =< f(p'_1, ..., p'I)

	Given f in M, we want an algorithm which yields us the subset L
of P* of locally maximal lists.   A list, l= (p_1, ..., p_I) is locally maximal
if for all lists l' = (p'_1, ..., p'_I):

	(for all i = 1...I, p_i =< p'_i)  implies
	f(p_1, ..., p_I) < f(p'_1, ..., p'I)

	(That's now a strict inequality).

*******************************************************************************

	Parenthetically, can I make a suggestion to a moderator.   Quite often,
problems associated with real projects appear here.   However, frequently, we
have difficulty in understanding what the underlying problem is, because the
problem is presented in a confused way, or information is omitted, or technical
terms which are not generally known appear.

	Also, often the problem as it is described is only a subpart of a wider
context, and in fact is not the correct problem to be addressing.  One needs
to know the wider context in order to advise what the best approach would be.
Also, regulars of this conference are just plain *curious* to know where a
certain abstract problem has cropped up.

	So, can I suggest a modification to 1.0, or alternatively
a 'set conference /notice="read note xxx"', which advises people who enter
this conference with real work related problems to:

	(1) State their problem as clearly and as completely as possible in 
language that a computer-illiterate person could understand.

	(2) Afterwards, include something about the context and the 
significance of the problem to the project.

*******************************************************************************

I'll put my ideas about solving the problem in hand in the next reply.

Regards,
Andrew.
1087.9HERON::BUCHANANAndrew @vbo DTN 828-5805Sat Jun 03 1989 12:0042
	With the definition of the problem as in -.1, there is no
interaction between f operating on lists of different length.   So let's
treat them independently.   Let N be the length of the lists we are
currently investigating.   Use the notation of -.1, and say P^N is the
set of lists of length N, over the positive integers.

	When searching for L, we'll need some kind of assumption about
how f behaves when the arguments take large values, otherwise you could
keep on searching for ever.   Eg.  suppose f(x) = LO forall x is a legitimate
function.   When does the algorithm stop computing f?   Perhaps the
orginator of the problem can provide an indication of what an appropriate
assumption might be.

N=0.   The empty list is locally maximal for all f in M.   It is possible
for it to be HI and still be locally maximal, something which is impossible
for all other N!

N=1.	L contains at most |Q|-1 elements.   If it contains exactly |Q|-1,
then f is uniquely defined by L.   To find L, calculate f(x) for x "as large
as is reasonable", and then try f(x/2) if necessary etc.

N=2.   Regard P^2 as a quarter plane.   L can be arbitrarily large but is
finite (if (x,y) is in L, then there at most x-1 + y-1 other lists in L
with the same value of f).   To find L, again divide and conquer seems to be
be most efficient.

It's clear that whatever finite value N takes, L is finite.   Suppose l =
(p_1,..p_N) is in L.   Then the range in which other lists in L with the
same f-value can be found is:

UNION ( i = 1..N) (c < p_i) X(i,c)

where X(i,c) = {(q_1,...q_N) such that q_i = c}

	But there are only a finite number of X(i,c), and by induction on N,
we can say that each X(i,c) contains only a finite number of elements of L.
Since Q itself is finite, L must be finite.

	Really, with no more knowledge of f, there's not much more one
can say, I think.

Andrew.
1087.1099.44% agreement...SLDA5::DUNAISKYFreedom isn't free.Mon Jun 05 1989 01:4443
    re: .6, .7
    
    right-on.... there will be more than one function, [depending on the
    data, user, etc.], but each function must meet the aforementioned
    criteria [which you've "forced" out of me ;-)].  Sorry again for not
    being totally clear...
    
    re: .8
    
    looks like an accurate and complete description of the problem (but
    then, i sure wouldn't be able to catch any glitches in those formulas,
    if there were any!)..  wish i could've stated it like that in .0!
    
    (as far as the parenthetical suggestions - i don't think my .0 would
    have been much different... at the time, i'm sure i thought i was being
    as understandable as possible!)
    
    re: .9
    
>	When searching for L, we'll need some kind of assumption about
>how f behaves when the arguments take large values, otherwise you could
>keep on searching for ever.   Eg.  suppose f(x) = LO forall x is a legitimate
>function.   When does the algorithm stop computing f?   Perhaps the
    
    as stated in .4 (i have the benefit of a print-out of all the replies
    so far!), we're assuming the function will change value over a
    "reasonable" period...  that assumption therefore becomes a necessary
    criteria for any functions we use, and [the function implementors] will
    have to ensure it is true.  the algorithm should then not have to take
    that example into consideration...
    
    one more "simplifying assumption" we can make (these things just keep
    coming): we will only have to deal with N>=2 (using .8,.9's
    definitions).
    
    about the "divide and conquer" approach... i think that was the heart
    of my question...  in fact, i have since gotten a "divide and conquer"
    approach worked out & [i believe] operating.  the next time i get a
    chance, i will try to describe this approach with respect to P*, Q,
    etc.
    
    thanks a bunch (especially for the re-"word"ing of the problem),
    Jonathan