Re: [R] combinatorics
Robin Hankin [EMAIL PROTECTED] 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 __ R-help@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.
[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 PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] combinatorics
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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Robin Hankin Sent: Friday, October 13, 2006 10:19 AM To: [EMAIL PROTECTED] 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 PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@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.
Re: [R] combinatorics
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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Robin Hankin Sent: Friday, October 13, 2006 10:19 AM To: [EMAIL PROTECTED] 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 PLEASE do read the posting guide http://www.R-project.org/posting- 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 PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] combinatorics
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 [EMAIL PROTECTED] 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@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? __ R-help@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.
Re: [R] combinatorics
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) [EMAIL PROTECTED] Fax-to-email: +44 (0)870 094 0861 Date: 13-Oct-06 Time: 17:40:20 -- XFMail -- __ R-help@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.
Re: [R] combinatorics
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@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:[EMAIL PROTECTED] UC San Diego http://biostat.ucsd.edu/~cberry/ La Jolla, San Diego 92093-0717 __ R-help@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.
Re: [R] combinatorics
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! The ruby permutations library (http://permutation.rubyforge.org/doc/index.html) references The Algorithm Design Manual, Steven S. Skiena, Telos/Springer, 1997, for permutation sequences. Hadley __ R-help@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.
Re: [R] combinatorics
-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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Robin Hankin Sent: Friday, October 13, 2006 10:19 AM To: [EMAIL PROTECTED] 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 PLEASE do read the posting guide http://www.R-project.org/posting- 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 PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. - -- Duncan Temple Lang[EMAIL PROTECTED] 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- __ R-help@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.
[R] combinatorics again
Hi I want to enumerate all vectors of length J, whose elements are integers in the range 1 to S, without regard to ordering. With J=S=3, the combinations are as follows: [,1] [,2] [,3] [1,]111 [2,]112 [3,]113 [4,]122 [5,]123 [6,]133 [7,]222 [8,]223 [9,]233 [10,]333 Note that (eg) c(1,2,1) is not on the list because we already have c(1,1,2) which would be equivalent [because the problem is to enumerate the cases without regard to ordering] and I do not want repeats. The best I can do is to create all S^J possibilities and weed out the repeats, using unique() ; code below. Why is this no good? Well, even for the tiny case of J=S=10, this would require a matrix of 10^10 rows, and my little linux machine refuses to cooperate, complaining about allocating a vector of length 1410065408. For these values of J and S, I happen to know that the are 6360 distinct combinations, which is eminently handleable. Anyone got any better ideas? allcomb - function(J,S){ f - function(...) { 1:S } out - as.matrix(do.call(expand.grid, lapply(1:J, FUN = f))) out - t(apply(out,1,sort)) unique(out) } -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Re: [R] combinatorics again
library(gtools) combinations(5,3) [,1] [,2] [,3] [1,]123 [2,]124 [3,]125 [4,]134 [5,]135 [6,]145 [7,]234 [8,]235 [9,]245 [10,]345 Robin Hankin a écrit : Hi I want to enumerate all vectors of length J, whose elements are integers in the range 1 to S, without regard to ordering. With J=S=3, the combinations are as follows: [,1] [,2] [,3] [1,]111 [2,]112 [3,]113 [4,]122 [5,]123 [6,]133 [7,]222 [8,]223 [9,]233 [10,]333 Note that (eg) c(1,2,1) is not on the list because we already have c(1,1,2) which would be equivalent [because the problem is to enumerate the cases without regard to ordering] and I do not want repeats. The best I can do is to create all S^J possibilities and weed out the repeats, using unique() ; code below. Why is this no good? Well, even for the tiny case of J=S=10, this would require a matrix of 10^10 rows, and my little linux machine refuses to cooperate, complaining about allocating a vector of length 1410065408. For these values of J and S, I happen to know that the are 6360 distinct combinations, which is eminently handleable. Anyone got any better ideas? allcomb - function(J,S){ f - function(...) { 1:S } out - as.matrix(do.call(expand.grid, lapply(1:J, FUN = f))) out - t(apply(out,1,sort)) unique(out) } -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html __ R-help@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
Re: [R] combinatorics again
Thank you Jacques but your solution misses (eg) c(1,1,2) which I need. best wishes Robin On 6 Mar 2006, at 09:17, Jacques VESLOT wrote: library(gtools) combinations(5,3) [,1] [,2] [,3] [1,]123 [2,]124 [3,]125 [4,]134 [5,]135 [6,]145 [7,]234 [8,]235 [9,]245 [10,]345 Robin Hankin a écrit : Hi I want to enumerate all vectors of length J, whose elements are integers in the range 1 to S, without regard to ordering. With J=S=3, the combinations are as follows: [,1] [,2] [,3] [1,]111 [2,]112 [3,]113 [4,]122 [5,]123 [6,]133 [7,]222 [8,]223 [9,]233 [10,]333 Note that (eg) c(1,2,1) is not on the list because we already have c(1,1,2) which would be equivalent [because the problem is to enumerate the cases without regard to ordering] and I do not want repeats. The best I can do is to create all S^J possibilities and weed out the repeats, using unique() ; code below. Why is this no good? Well, even for the tiny case of J=S=10, this would require a matrix of 10^10 rows, and my little linux machine refuses to cooperate, complaining about allocating a vector of length 1410065408. For these values of J and S, I happen to know that the are 6360 distinct combinations, which is eminently handleable. Anyone got any better ideas? allcomb - function(J,S){ f - function(...) { 1:S } out - as.matrix(do.call(expand.grid, lapply(1:J, FUN = f))) out - t(apply(out,1,sort)) unique(out) } -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting- guide.html -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Re: [R] combinatorics again
Robin Hankin wrote: Thank you Jacques but your solution misses (eg) c(1,1,2) which I need. See ?combinations which should point you to combinations(5,3, repeats.allowed=TRUE) Best, Uwe best wishes Robin On 6 Mar 2006, at 09:17, Jacques VESLOT wrote: library(gtools) combinations(5,3) [,1] [,2] [,3] [1,]123 [2,]124 [3,]125 [4,]134 [5,]135 [6,]145 [7,]234 [8,]235 [9,]245 [10,]345 Robin Hankin a écrit : Hi I want to enumerate all vectors of length J, whose elements are integers in the range 1 to S, without regard to ordering. With J=S=3, the combinations are as follows: [,1] [,2] [,3] [1,]111 [2,]112 [3,]113 [4,]122 [5,]123 [6,]133 [7,]222 [8,]223 [9,]233 [10,]333 Note that (eg) c(1,2,1) is not on the list because we already have c(1,1,2) which would be equivalent [because the problem is to enumerate the cases without regard to ordering] and I do not want repeats. The best I can do is to create all S^J possibilities and weed out the repeats, using unique() ; code below. Why is this no good? Well, even for the tiny case of J=S=10, this would require a matrix of 10^10 rows, and my little linux machine refuses to cooperate, complaining about allocating a vector of length 1410065408. For these values of J and S, I happen to know that the are 6360 distinct combinations, which is eminently handleable. Anyone got any better ideas? allcomb - function(J,S){ f - function(...) { 1:S } out - as.matrix(do.call(expand.grid, lapply(1:J, FUN = f))) out - t(apply(out,1,sort)) unique(out) } -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting- guide.html -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html __ R-help@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
Re: [R] combinatorics again
combinations(5,3,rep=T) Robin Hankin a écrit : Thank you Jacques but your solution misses (eg) c(1,1,2) which I need. best wishes Robin On 6 Mar 2006, at 09:17, Jacques VESLOT wrote: library(gtools) combinations(5,3) [,1] [,2] [,3] [1,]123 [2,]124 [3,]125 [4,]134 [5,]135 [6,]145 [7,]234 [8,]235 [9,]245 [10,]345 Robin Hankin a écrit : Hi I want to enumerate all vectors of length J, whose elements are integers in the range 1 to S, without regard to ordering. With J=S=3, the combinations are as follows: [,1] [,2] [,3] [1,]111 [2,]112 [3,]113 [4,]122 [5,]123 [6,]133 [7,]222 [8,]223 [9,]233 [10,]333 Note that (eg) c(1,2,1) is not on the list because we already have c(1,1,2) which would be equivalent [because the problem is to enumerate the cases without regard to ordering] and I do not want repeats. The best I can do is to create all S^J possibilities and weed out the repeats, using unique() ; code below. Why is this no good? Well, even for the tiny case of J=S=10, this would require a matrix of 10^10 rows, and my little linux machine refuses to cooperate, complaining about allocating a vector of length 1410065408. For these values of J and S, I happen to know that the are 6360 distinct combinations, which is eminently handleable. Anyone got any better ideas? allcomb - function(J,S){ f - function(...) { 1:S } out - as.matrix(do.call(expand.grid, lapply(1:J, FUN = f))) out - t(apply(out,1,sort)) unique(out) } -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting- guide.html -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Re: [R] combinatorics again
Patrick, Uwe thanks! [both your solutions were conceptually identical, except for one was ascending and one was descending] very best wishes Robin On 6 Mar 2006, at 09:36, Uwe Ligges wrote: Robin Hankin wrote: Thank you Jacques but your solution misses (eg) c(1,1,2) which I need. See ?combinations which should point you to combinations(5,3, repeats.allowed=TRUE) Best, Uwe best wishes Robin On 6 Mar 2006, at 09:17, Jacques VESLOT wrote: library(gtools) combinations(5,3) [,1] [,2] [,3] [1,]123 [2,]124 [3,]125 [4,]134 [5,]135 [6,]145 [7,]234 [8,]235 [9,]245 [10,]345 Robin Hankin a écrit : Hi I want to enumerate all vectors of length J, whose elements are integers in the range 1 to S, without regard to ordering. With J=S=3, the combinations are as follows: [,1] [,2] [,3] [1,]111 [2,]112 [3,]113 [4,]122 [5,]123 [6,]133 [7,]222 [8,]223 [9,]233 [10,]333 Note that (eg) c(1,2,1) is not on the list because we already have c(1,1,2) which would be equivalent [because the problem is to enumerate the cases without regard to ordering] and I do not want repeats. The best I can do is to create all S^J possibilities and weed out the repeats, using unique() ; code below. Why is this no good? Well, even for the tiny case of J=S=10, this would require a matrix of 10^10 rows, and my little linux machine refuses to cooperate, complaining about allocating a vector of length 1410065408. For these values of J and S, I happen to know that the are 6360 distinct combinations, which is eminently handleable. Anyone got any better ideas? allcomb - function(J,S){ f - function(...) { 1:S } out - as.matrix(do.call(expand.grid, lapply(1:J, FUN = f))) out - t(apply(out,1,sort)) unique(out) } -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting- guide.html -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting- guide.html __ R-help@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 -- 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 PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html