# Re: [R] combinatorics

From: Robin Hankin <r.hankin_at_noc.soton.ac.uk>
Date: Fri 13 Oct 2006 - 15:37:34 GMT

Hi Christos

thanks for this. Unfortunately, this approach wouldn't work for me because the real problem is too big for it: I have letters A-F and two of each, giving

12!/(2^6) ~= 7e6 combinations (borderline feasible)

But in the approach you coded up below, matrix zz would have   6^12 ~= 2e9 rows before eliminating the non-feasible ones. This is too big for me.

Looks like it's going to be another weekend lost to C [but at least I now have some confidence that I've not overlooked anything obvious!]

With very best wishes, I really appreciate your efforts

Robin

On 13 Oct 2006, at 16:21, Christos Hatzis wrote:

> Hi Robin,
>
> This approach first generates all combinations and then eliminates the
> non-feasible ones. It should work fine for smallish vectors but
> might not
> scale well for larger vectors. Hopefully it gives you what you
> need for
> this problem.
>
> xx <- c("A","A","B","B","C")
> yy <- 1:length(xx)
> zz <- expand.grid(yy,yy,yy,yy,yy)
>
> ss <- zz[ apply(zz, 1, FUN=function(x) length(unique(x))) == length
> (xx), ]
> ss <- as.matrix(ss)
>
> pp <- apply(ss, 1, FUN=function(x,v) paste(v[as.vector(x)],
> collapse=""),
> v=xx)
> res <- unique(pp)
>
>> res
> [1] "CBBAA" "BCBAA" "BBCAA" "CBABA" "BCABA" "CABBA" "ACBBA"
> "BACBA" "ABCBA"
> "BBACA" "BABCA"
> [12] "ABBCA" "CBAAB" "BCAAB" "CABAB" "ACBAB" "BACAB" "ABCAB"
> "CAABB" "ACABB"
> "AACBB" "BAACB"
> [23] "ABACB" "AABCB" "BBAAC" "BABAC" "ABBAC" "BAABC" "ABABC" "AABBC"
>> length(res)
> [1] 30
>
> -Christos
>
> Christos Hatzis, Ph.D.
> Nuvera Biosciences, Inc.
> 400 West Cummings Park
> Suite 5350
> Woburn, MA 01801
> Tel: 781-938-3830
> www.nuverabio.com
>
>
> -----Original Message-----
> From: r-help-bounces@stat.math.ethz.ch
> [mailto:r-help-bounces@stat.math.ethz.ch] On Behalf Of Robin Hankin
> Sent: Friday, October 13, 2006 10:19 AM
> To: R-help@r-project.org
> Subject: [R] combinatorics
>
> Hi
>
> How do I generate all ways of ordering sets of indistinguishable
> items?
>
> suppose I have two A's, two B's and a C.
>
> Then I want
>
> AABBC
> AABCB
> AACBC
> ABABC
> . . .snip...
> BBAAC
> . . .snip...
> CBBAA
>
> [there are 5!/(2!*2!) = 30 arrangements. Note AABBC != BBAAC]
>
> How do I do this?
>
>
>
>
>
> --
> Robin Hankin
> Uncertainty Analyst
> National Oceanography Centre, Southampton European Way, Southampton
> SO14
> 3ZH, UK
> tel 023-8059-7743
>
> ______________________________________________
> R-help@stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
>

```--
Robin Hankin
Uncertainty Analyst
National Oceanography Centre, Southampton
European Way, Southampton SO14 3ZH, UK
tel  023-8059-7743

______________________________________________
R-help@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help