fundamental principles of counting - 2nd try

Hi Wolfgang,

for listing you events you may find these functions useful:

NO ORDER, WITH REPETITION:
(%i1) list_multisets(lst, card) :=
    if card=0 then [[]]
    else if length(lst)=1 then [makelist(first(lst), card)]
    else append(
        map(lambda([ms], cons(first(lst), ms)), list_multisets(lst, card-1)),
        list_multisets(rest(lst), card))$
(%i2) list_multisets([1,2,3,4], 2);
(%o2) [[1,1],[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,3],[3,4],[4,4]]

NO ORDER, NO REPETITION:
(%i3) list_sets(lst, card) :=
    if card=0 then [[]]
    else if card>length(lst) then []
    else append(
        map(lambda([ms], cons(first(lst), ms)),
list_multisets(rest(lst), card-1)),
        list_sets(rest(lst), card))$
(%i4) list_sets([1,2,3,4], 2);
(%o4) [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

WITH ORDER WITH REPETITION:
(%i5) list_sequences(lst, card) :=
    if card=0 then [[]]
    else create_list(cons(e,l), e, lst, l, list_sequences(lst, card-1))$
(%i6) list_sequences([1,2,3,4], 2);
(%o6) [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]

WITH ORDER NO REPETITION:
(%i7) list_sequences1(lst, card) :=
    if card=0 then [[]]
    else if length(lst)<card then []
    else xreduce(append,
        makelist(
            map(lambda([s], cons(e, s)),
                list_sequences1(delete(e, lst), card-1)),
            e, lst))$
(%i8) list_sequences1([1,2,3,4], 2);
(%o8) [[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

I haven't looked at the random generation functions carefully, but
nOwR does not select multisets uniformly (it will select [1,2,3] more
often than [1,1,1]).

HTH, Andrej

On Fri, Aug 6, 2010 at 12:58 PM, Wolfgang Lindner <LindnerW at t-online.de> wrote:
> dear group,
>
> coming back from a break I found no reaction to my query:
>
> |But I don't find functions to list (not only count) all
> |. arrangements of s (whose number is n^r )
> ||. combinations of s (whose number is C(n,r) )
> |. variations of s ? (:= all combs with repetitons,
> | ?there are C(n+r-1,r) many of them and we want to see them all)
>
> Maybe I was not explicit enough ..
> but I would like to do elementary discrete math with Maxima.
>
> So I will elaborate a bit, give a partial answer
> and ask for a solution to concrete question.
>
> 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 ..
>
> (%i223) S : {1,2,3,4}$
> ? ? ? ?S2 : cartesian_product (S, S);
>
> Q2: do you see possibilities to 'optimise' my code
> ? ?for the 4 cases of counting? see below
>
> Q3: how to write a better version of Events_nOwR(n,k), see below?
>
> HERE is my code.
> Any hints are very welcome,
>
> hth Wolfgang
>
> ------------------------------------------------------------
> Fundamental principles of Counting with MAXIMA: (W. Lindner)
> ------------------------------------------------------------
>
> 1. LISTING OF ALL ELEMENTAY EVENTS WITH MAXIMA.
>
> According to the attachment we have 4 cases.
>
> 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]]
>
> case 2: wOwR (with order, with repetitions)
> Problem: how to write function Events_wOwR(n,r),
> ? ? ? ? e.g. how to produce a sequence of k instances of S
> ? ? ? ? to call cartesian_product(S,S,..,S) ??
>
> (%i223) S : {1,2,3,4}$
> ? ? ? ?S2 : cartesian_product (S, S);
> ? ? ? ?listify(S2);
> ? ? ? ?cardinality(S2);
>
> (%o224)
> {[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,
> 1],[4,2],[4,3],[4,4]}
> (%o225)
> [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,
> 1],[4,2],[4,3],[4,4]]
> (%o226) 16
>
> case 3: wOnR (with order, no repetitions)
> problem: .. using result of case 2 ..
>
> (%i273) Events_wOnR(n,r) := listify(subset (S2, lambda ([x], is(
> cardinality(setify(x))=k))))$
> ? ? ? ?Events_nOnR(4,2);
>
> (%o274) [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
>
> case 4: nOwR (no order, with repetitions)
> ? ? ? ?we have 10 elementary events:
> ElEr: 1 1 [1,1] (ElEr = elementary event)
> ? ? ?1 2
> ? ? ?1 3
> ? ? ?1 4
> ? ? ?2 2
> ? ? ?..
> ? ? ?3 4
> ? ? ?4 4 -> length=10
>
> (%i281) Events_nOwR (n,k) := block(
> ElEr : makelist([i],i,1,n),
> for j:2 thru k do (
> ?ElErNew: [],
> ?for m:1 thru length(ElEr) do
> ? ?for r : ElEr[m][j-1] thru n do
> ? ? ? ?ElErNew: append( ElErNew, [append(ElEr[m],[r])] ),
> ?ElEr : ElErNew
> ?),
> ?sublist(ElEr, lambda ([x], x[1]));
>
>
> (%i282) Events_nOwR(4,2);
> (%o282) [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
>
> 2. URN-MODELLS:
>
> Urnmodell nOwR, one draw (with repetions and no order)
> Comment: 'sort' destroys the distinguish steps of the drawing!
>
> (%i254) ?nOwR(n,r) := sort(makelist(random(n)+1, k,1,n-r))$
> ? ? ? ? nOwR(4,2);
> (%o248) [1,4]
>
> Urnmodell nOnR, one draw:
>
> (%i255) nOnR(n,r) := sort(rest (random_permutation (makelist(i,i,1,n)),
> n-r))$
> ? ? ? ?nOnR(4,2);
> (%o248) [1,4]
>
> Urnmodell wOwR, one draw:
>
> (%i263) wOwR(n,r) := makelist(random(n)+1, k,1,r)$
> ? ? ? ?wOwR(4,2);
> (%o256) [2,3]
>
> Urnmodell wOnR, one draw:
>
> (%i265) wOnR(n,r) := rest (random_permutation (makelist(i,i,1,n)), n-r)$
> ? ? ? ?wOnR(4,2);
> (%o264) [3,1]
>
>
>
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>