Efficient way to code "(symbol,multiplicity)-counting" - how?

[Mark Phillips]

Dylan Thurston wrote:

 > On Thu, May 23, 2002 at 04:44:25PM +0930, Mark Phillips wrote:
 > ...
 >
 >>We "count" as follows:
 >>[] [x] [y] [z] [x,y] [x,z] [y,x] [y,y] [y,z] [z,x] [z,y] [x,y,y] [x,y,z]
 >>[x,z,y] [y,x,y] [y,x,z] [y,y,x] [y,y,z] [y,z,x] [y,z,y] [z,x,y] [z,y,x]
 >>[z,y,y] [x,y,y,z] [x,y,z,y] [x,z,y,y] [y,x,y,z] [y,x,z,y] [y,y,x,z]
 >>[y,y,z,x] [y,z,x,y] [y,z,y,x] [z,x,y,y] [z,y,x,y] [z,y,y,x]
 >>and then start back at the beginning again (with []).
 >>
 >>I want to define a function
 >>next :: [(a,Int)] -> [a] -> [a]
 >>
 >
 > Is there a reason you frame the problem this way?  Would it be OK to
 > give a function
 >
 >
 >>count :: [(a,Int)] -> [[a]]
 >>
 >
 > which would return, e.g., the list you gave above?  That would
 > probably be more natural to code.


I'm not sure this is enough.  However what might be enough, an
alternative way to frame the problem, would be to have a function
which returns a partial list, given some starting point.  Ie

count :: [(a,Int)] -> [a] -> [[a]]

What I am using this counting for is to solve the following problem:

Suppose you have 3 boxes (more generally n boxes) in a line, and you
have symbols with certain multiplicities as before.  I wish to put a
list of symbols into each box such that

* the total number of occurrences of any given symbol, across all boxes,
    should equal its multiplicity (ie all symbols should be used the
    right number of times)
* the lists, going from left to right along the boxes, should be
    increasing (using the above "counting" definition to define the
    ordering) (so the next box along should contain a sequence that is
    greater than or equal to the previous one)

For a given (symbol,multiplicity) list and a fixed number of boxes, n
say, I wish to generate all such choices of symbol lists (ie all
choices of lists which satisfy the above conditions).

My idea for solving the problem is to choose the first box, starting
from [] and incrementing using the above counting method.  Then at
each step, consider objects for the second box, starting from whatever
was in the firxt box and incrementing from there,... and so on.

That is what my "next" function is for.  To do the incrementing from
where the previous box left off.  So as you can see, I do need to be
able to start part way through the list.

Of course, maybe I am not approaching the problem in the best manner.

Cheers,

Mark.

-- 
Dr Mark H Phillips
Research Analyst (Mathematician)

AUSTRICS - Smarter Scheduling Solutions - www.austrics.com

Level 2, 50 Pirie Street, Adelaide SA 5000, Australia
Phone +61 8 8226 9850
Fax   +61 8 8231 4821
Email mark@austrics.com.au