all combinations with replacement not ordered

-----Original Message-----
From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On Behalf
Of Konstantin Tretiakov
Sent: Thursday, November 07, 2013 5:38 AM
To: r-help at r-project.org
Subject: [R] all combinations with replacement not ordered

Hello!

I need to obtain all possible combinations with replacement when order is
not important.
E.g. I have a population x{1,2,3}.
So I can get (choose(3+3-1,3)=) 10 combinations from this population with
'size=3'.
How can I get a list of all that combinations?

I have tried 'expand.grid()' and managed to get only samples where order is
important.
'combn()' gave me samples without replacement.

Best regards,
Konstantin Tretyakov.

	[[alternative HTML version deleted]]

Hello!

I need to obtain all possible combinations with replacement when
order is not important.
E.g. I have a population x{1,2,3}.
So I can get (choose(3+3-1,3)=) 10 combinations from this population
with 'size=3'.
How can I get a list of all that combinations?

I have tried 'expand.grid()' and managed to get only samples where
order is important.
'combn()' gave me samples without replacement.

Best regards,
Konstantin Tretyakov.

From your description I infer that, from {1,2,3}, you want the result:

On 07-Nov-2013 13:38:29 Konstantin Tretiakov wrote:

Hello!

I need to obtain all possible combinations with replacement when
order is not important.
E.g. I have a population x{1,2,3}.
So I can get (choose(3+3-1,3)=) 10 combinations from this population
with 'size=3'.
How can I get a list of all that combinations?

I have tried 'expand.grid()' and managed to get only samples where
order is important.
'combn()' gave me samples without replacement.

Best regards,
Konstantin Tretyakov.

From your description I infer that, from {1,2,3}, you want the result:

  1 1 1
  1 1 2
  1 1 3
  1 2 2
  1 2 3
  1 3 3
  2 2 2
  2 2 3
  2 3 3
  3 3 3

The following will do that:

u <- c(1,2,3)
unique(t(unique(apply(expand.grid(u,u,u),1,sort),margin=1)))

#      [,1] [,2] [,3]
# [1,]    1    1    1
# [2,]    1    1    2
# [3,]    1    1    3
# [4,]    1    2    2
# [5,]    1    2    3
# [6,]    1    3    3
# [7,]    2    2    2
# [9,]    2    3    3
#[10,]    3    3    3

There may be a simpler way!
Ted.

-------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at wlandres.net>
Date: 07-Nov-2013  Time: 17:04:50
This message was sent by XFMail

Well, you can create the expand.grid data frame programmatically via:

u <- 1:3
len <- length(u)
v <-do.call(expand.grid, split(rep(u,len),rep(seq_len(len),e=len)))

And then you can use unique.array to get the unique rows after the sort:

unique(t(apply(v,1,sort)))

However, I agree with your sentiments. Not only does this seem
inelegant, but it will not scale well.

I would imagine a recursive approach would be more efficient -- as
then only the sets you need would be produced and there'd be no
sorting, etc. -- but I have neither the time nor interest to work it
out.

... and I bet someone already has done this in some R package anyway.

Cheers,
Bert

On Thu, Nov 7, 2013 at 9:04 AM, Ted Harding <Ted.Harding at wlandres.net> wrote:

On 07-Nov-2013 13:38:29 Konstantin Tretiakov wrote:

Hello!

I need to obtain all possible combinations with replacement when
order is not important.
E.g. I have a population x{1,2,3}.
So I can get (choose(3+3-1,3)=) 10 combinations from this population
with 'size=3'.
How can I get a list of all that combinations?

I have tried 'expand.grid()' and managed to get only samples where
order is important.
'combn()' gave me samples without replacement.

Best regards,
Konstantin Tretyakov.

From your description I infer that, from {1,2,3}, you want the result:

  1 1 1
  1 1 2
  1 1 3
  1 2 2
  1 2 3
  1 3 3
  2 2 2
  2 2 3
  2 3 3
  3 3 3

The following will do that:

u <- c(1,2,3)
unique(t(unique(apply(expand.grid(u,u,u),1,sort),margin=1)))

#      [,1] [,2] [,3]
# [1,]    1    1    1
# [2,]    1    1    2
# [3,]    1    1    3
# [4,]    1    2    2
# [5,]    1    2    3
# [6,]    1    3    3
# [7,]    2    2    2
# [9,]    2    3    3
#[10,]    3    3    3

There may be a simpler way!
Ted.

-------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at wlandres.net>
Date: 07-Nov-2013  Time: 17:04:50
This message was sent by XFMail

--

Bert Gunter
Genentech Nonclinical Biostatistics

(650) 467-7374