[R] [OT] Combinatorials wtih constraints

[Greg Snow]

Well here is one way (but this finds too many, then reduces, so if the final result is near the memory limit, this would go over first):

unique(t(combn( rep(LETTERS[1:5], each=2), 3)))

-- 
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.snow at imail.org
801.408.8111


> -----Original Message-----
> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-
> project.org] On Behalf Of Ted Harding
> Sent: Thursday, June 24, 2010 2:53 PM
> To: Doran, Harold
> Cc: r-help at r-project.org
> Subject: Re: [R] [OT] Combinatorials wtih constraints
> 
> On 24-Jun-10 19:47:38, Doran, Harold wrote:
> > This is not an R question, but a question on some combinatorial
> > mathematics. Apologies for the OT if it is wildy inappropriate.
> > The traditional C(n.k) method tells me how many combinations k
> > I can make with n objects. However, suppose I want the number of
> > combinations where an object cannot be used more than Q times
> > where Q is a parameter that changes?
> >
> > For instance:
> >
> > combn(LETTERS[1:5], 3)
> >
> > shows the number of triplets I can make with the 5 letters.
> > But, suppose I want the constraint that no letter can be used
> > more than twice (Q).
> >
> > Are there well-known methods for identifying the number of possible
> > combinations with this kind of constraint?
> >
> > Thanks,
> > Harold
> 
> I think there is some confusion in the statement of the problem.
> "C(n,k)" gives the number of ways of choosing k distinct objects
> out of n distinct objects, so there is no repetition of an object
> in any of the selections of k objects. This can be observed in the
> result of your "combn(LETTERS[1:5], 3)" command:
> 
> combn(LETTERS[1:5], 3)
> #      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
> # [1,] "A"  "A"  "A"  "A"  "A"  "A"  "B"  "B"  "B"  "C"
> # [2,] "B"  "B"  "B"  "C"  "C"  "D"  "C"  "C"  "D"  "D"
> # [3,] "C"  "D"  "E"  "D"  "E"  "E"  "D"  "E"  "E"  "E"
> 
> So no letter is used more than once, let alone more than twice,
> so it is maximally constrained!
> 
> Is it the case that your question is
> 
>   In how many ways can we choose k objects out of n distinct
>   objects, with repetition allowed, but with no more than Q
>   replicates of any object in the selection?
> 
> If so, I'm not sure whether there is an R function which will
> handle it directly, and as a combinatorial problem it is one
> where you can quite easily drop stitches; so if there isn't
> one I'll wait for confirmation before thinking about how to
> implement it in R!
> 
> There may be some mileage in the 'partitions' package, see e.g.
> 
> http://finzi.psych.upenn.edu/R/library/partitions/html/
> partitions.package.html
> 
> but I think one would need to experiment with it a bit in order
> to be sure what the functions do.
> 
> Ted.
> 
> --------------------------------------------------------------------
> E-Mail: (Ted Harding) <Ted.Harding at manchester.ac.uk>
> Fax-to-email: +44 (0)870 094 0861
> Date: 24-Jun-10                                       Time: 21:51:49
> ------------------------------ XFMail ------------------------------
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-
> guide.html
> and provide commented, minimal, self-contained, reproducible code.