fundamental principles of counting - 2nd try

On Fri, Aug 6, 2010 at 06:58, Wolfgang Lindner <LindnerW at t-online.de> wrote:

> Q1: If S is a set, how to produce a sequence of k instances
>    of S e.g. to call cartesian_product(S,S,..S)?
>    makelist(S,i,1,k) don't work ..
>

apply(cartesian_product, makelist(S,i,1,k))

case 1: nOnR (no order, no repetitions)
>
> (%i269) Events_nOnR(n,r) := full_listify(powerset
> (setify(makelist(i,i,1,n)), n-r))$
>        Events_nOnR(4,2);
> (%o270) [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
>

I would recommend that you write some basic functions to keep your code
clean and simple, e.g.

natural_n(n):=makelist(i,i,1,n)$
range(m,n):=if m>n+1 then [] else makelist(i,i,m,n)$    << handling of cases
like range(5,1) is up to you of course

I do not recommend using full_listify.  If at some point your code is
generalized to handle arbitrary objects, not just numbers, then it will do
the wrong thing in some cases.  For example,

cartesian_product({a,b},{c,{d}}) =>  {[a, c], [a, {d}], [b, c], [b, {d}]}
 -- Good
listify(cartesian_product({a,b},{c,{d}})) => [[a, c], [a, {d}], [b, c], [b,
{d}]]  -- Good
full_listify(cartesian_product({a,b},{c,{d}})) => [[a, c], [a, [d]], [b, c],
[b, [d]]]  -- Oops! The object {d} was incorrectly made into a list

(%i273) Events_wOnR(n,r) := listify(subset (S2, lambda ([x], is(
> cardinality(setify(x))=k))))$
>        Events_nOnR(4,2);
>

In combinatory algorithms like this, taking subsets of a full cartesian
product is bound to be inefficient.  But maybe you only care about small
cases?

Have you looked at Knuth Volume 4?  Several fascicles have been published,
and it is all about combinatorial algorithms.

               -s