Re: Combinatorical efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg40807] Re: Combinatorical efficiency
- From: Erich Neuwirth <erich.neuwirth at aon.at>
- Date: Sat, 19 Apr 2003 22:59:14 -0400 (EDT)
- References: <b6tsrc$n1l$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Here is another attempt
Combinations with replacment
n objects too choose from,
k objects to be chosen
can be represented as
nondecreasing sequences of of length k
with the last element not exceeding n.
combinations without replacement are strictly increasing seqeunces
with the last element not exceeding n.
SO here sre functions prroducing all these sequences,
and nothing more.
ExtendIncr[Seq_, Upper_] := Map[Append[Seq, #] &, Range[
Seq[[-1]] + 1, Upper]]
ExtendNonDecr[Seq_, Upper_] := Map[Append[Seq, #] &, Range[Seq[[-1]],
Upper]]
IncrSeq[1, Upper_] := Table[{i}, {i, 1, Upper}]
IncrSeq[Len_,
Upper_] := Flatten[Map[ExtendIncr[#, Upper] &, IncrSeq[Len - 1,
Upper]], 1]
NonDecrSeq[1, Upper_] := Table[{i}, {i, 1, Upper}]
NonDecrSeq[
Len_, Upper_] := Flatten[Map[ExtendNonDecr[#, Upper] &, IncrSeq[Len -
1, Upper]], 1]