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
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
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Use 'permutations' in 'gtools'
x <- permutations(5,5)
y <- c('a','a','b','b','c')[x]
dim(y) <- dim(x)
unique(y)
On 10/13/06, Robin Hankin <r.hankin at noc.soton.ac.uk>
wrote:> 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
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
--
Jim Holtman
Cincinnati, OH
+1 513 646 9390
What is the problem you are trying to solve?
On 13-Oct-06 Robin Hankin wrote:> 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 ---->> I think you mean AACBB here! > ABABC > . . .snip... > BBAAC > . . .snip... > CBBAA > > [there are 5!/(2!*2!) = 30 arrangements. Note AABBC != BBAAC] > > How do I do this?I've tried to think of an efficient and economical (and therefore clever) way of doing this for larger problems; but that will have to wait for another day! Meanwhile, a problem of the order of the one you describe above can be solved quite slickly: X<-c("A","A","B","B","C") library(combinat) ##[result below stripped of " quotes for clarity] unique(array(permn(X))) [[1]] [1] A A B B C [[2]] [1] A A B C B [[3]] [1] A A C B B [[4]] [1] A C A B B [[5]] [1] C A A B B [[6]] [1] A B A B C [[7]] [1] A B A C B [[8]] [1] A B C A B [[9]] [1] A C B A B [[10]] [1] C A B A B [[11]] [1] C B A A B [[12]] [1] B C A A B [[13]] [1] B A C A B [[14]] [1] B A A C B [[15]] [1] B A A B C [[16]] [1] B A B A C [[17]] [1] B A B C A [[18]] [1] B A C B A [[19]] [1] B C A B A [[20]] [1] C B A B A [[21]] [1] C A B B A [[22]] [1] A C B B A [[23]] [1] A B C B A [[24]] [1] A B B C A [[25]] [1] A B B A C [[26]] [1] B B A A C [[27]] [1] B B A C A [[28]] [1] B B C A A [[29]] [1] B C B A A [[30]] [1] C B B A A However, the above simple function will quickly get short of breath if the total number of items gets much above, say 10. Hoping this helps! Ted. -------------------------------------------------------------------- E-Mail: (Ted Harding) <Ted.Harding at nessie.mcc.ac.uk> Fax-to-email: +44 (0)870 094 0861 Date: 13-Oct-06 Time: 17:40:20 ------------------------------ XFMail ------------------------------
On Fri, 13 Oct 2006, Robin Hankin wrote:> 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?I'd recursively use combn() to choose locations for A's, then B's, then ...> where.A <- combn(5,2)[, rep( 1:choose(5,2), each = choose(3,2)*choose(1,1))] > where.not.A <- apply(where.A,2,function(x) (1:5)[-x]) > where.B <- matrix(apply(unique( where.not.A, MARGIN=2), 2, combn, 2 ),nr=2) > where.not.AB <- apply(rbind(where.A,where.B),2,function(x) (1:5)[-x] ) > result <- matrix("C",nr=5,nc=30) > result[ cbind( c( where.A ), c( col( where.A ) ) ) ] <- "A" > result[ cbind( c( where.B ), c( col( where.B ) ) ) ] <- "B" > cbind( apply(result,2,paste,collapse="") )[,1] [1,] "AABBC" [2,] "AABCB" [3,] "AACBB" . . .> > -- > 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 > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >Charles C. Berry (858) 534-2098 Dept of Family/Preventive Medicine E mailto:cberry at tajo.ucsd.edu UC San Diego http://biostat.ucsd.edu/~cberry/ La Jolla, San Diego 92093-0717
Robin Hankin <r.hankin at noc.soton.ac.uk> writes:> 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?See Knuth, The Art of Computer Programming Vol 4, Fascicle 3 and 4. Jens