# Re: [R] [OT] Combinatorials wtih constraints

From: Ted Harding <Ted.Harding_at_manchester.ac.uk>
Date: Thu, 24 Jun 2010 22:42:13 +0100 (BST)

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 ------------------------------

______________________________________________
```
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. Received on Thu 24 Jun 2010 - 21:44:07 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Thu 24 Jun 2010 - 22:00:37 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.