[R] [OT] Combinatorials wtih constraints

[(Ted Harding)]

That's neat, Greg! (As code, anyway). There was I, thinking about
how best to build it up by construction, then your "slash-and-burn"
technique does it in one line.

But was this the right problem, or the alternative that Bert Gunter
suggested?
Ted.

On 24-Jun-10 21:06:06, Greg Snow wrote:
> 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.
> 
> ______________________________________________
> 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.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at manchester.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 24-Jun-10                                       Time: 22:42:10
------------------------------ XFMail ------------------------------