# [R] combinatorics

Duncan Temple Lang duncan at wald.ucdavis.edu
Sat Oct 14 01:44:25 CEST 2006

```-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Robin.

When I saw this, I thought expand.grid would do.
But since it is too big and since I sympathize
that C isn't the ideal use of ones time, perhaps
the Combinations package on www.omegahat.org
might be helpful.  This provides a "one-at-a-time"
approach.

D.

Robin Hankin wrote:
> 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 at stat.math.ethz.ch
>>[mailto:r-help-bounces at stat.math.ethz.ch] On Behalf Of Robin Hankin
>>Sent: Friday, October 13, 2006 10:19 AM
>>To: R-help at 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 at 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 at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> and provide commented, minimal, self-contained, reproducible code.

- --
Duncan Temple Lang                    duncan at wald.ucdavis.edu
Department of Statistics              work:  (530) 752-4782
4210 Mathematical Sciences Building   fax:   (530) 752-7099
One Shields Ave.
University of California at Davis
Davis,
CA 95616,
USA
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (Darwin)

iD8DBQFFMCTY9p/Jzwa2QP4RAiCiAJ9APb87RkA7Ap1Y8BigNtmI3Q8oAQCfRzfp
3+v/Ari5BVD5/5hDYDIVzWY=
=8NBK
-----END PGP SIGNATURE-----

```