Thread Subject: NchooseK

Hello -

I have problem of memory when I run: NK=nchoosek (1:N,K), in which N is >40. I need to generate a "NK", wherein "N" is 140. Does anyone know how I could deal with this problem?!

Thanks,
Farnk

"Frank Sabouri" <Frank.Sabouri@gmail.com> wrote in message <hn6mt9$9kb$1@fred.mathworks.com>...
> Hello -
>
> I have problem of memory when I run: NK=nchoosek (1:N,K), in which N is >40. I need to generate a "NK", wherein "N" is 140. Does anyone know how I could deal with this problem?!
>

Rather than just blindly trying to do something, THINK
first. How many combinations are you hoping to
generate? Just for kicks, try this:

nchoosek(140,70)
Warning: Result may not be exact. Coefficient is greater than 1.000000e+15 and is only accurate to 15 digits
> In nchoosek at 66
ans =
   9.3821e+40

Let me see. 10^41 different combinations, suggests
you will need on the order of multiple tredecillion bytes
of memory. Do you really have that big of a computer?
In fact, the number of atoms in the entire Earth is
roughly that large.

http://pages.prodigy.net/jhonig/bignum/qaearth.html

The way to deal with your problem is to make your
problems SMALLER. Your computer is not infinitely
large or infinitely fast.

John

Hello -

Let me ask my question in other way: I have a matrix of data (140X15), I want to randomly generate as much as possible sub-matrices (6X15). It was why I used "nchoosek" to randomly set the sub-matices. There is any function that allow me to creat these submatices.

Frank

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <hn6nra$8rc$1@fred.mathworks.com>...
> "Frank Sabouri" <Frank.Sabouri@gmail.com> wrote in message <hn6mt9$9kb$1@fred.mathworks.com>...
> > Hello -
> >
> > I have problem of memory when I run: NK=nchoosek (1:N,K), in which N is >40. I need to generate a "NK", wherein "N" is 140. Does anyone know how I could deal with this problem?!
> >
>
> Rather than just blindly trying to do something, THINK
> first. How many combinations are you hoping to
> generate? Just for kicks, try this:
>
> nchoosek(140,70)
> Warning: Result may not be exact. Coefficient is greater than 1.000000e+15 and is only accurate to 15 digits
> > In nchoosek at 66
> ans =
> 9.3821e+40
>
> Let me see. 10^41 different combinations, suggests
> you will need on the order of multiple tredecillion bytes
> of memory. Do you really have that big of a computer?
> In fact, the number of atoms in the entire Earth is
> roughly that large.
>
> http://pages.prodigy.net/jhonig/bignum/qaearth.html
>
> The way to deal with your problem is to make your
> problems SMALLER. Your computer is not infinitely
> large or infinitely fast.
>
> John

Frank Sabouri wrote:
> Hello -
>
> I have problem of memory when I run: NK=nchoosek (1:N,K), in which N is
> >40. I need to generate a "NK", wherein "N" is 140. Does anyone know
> how I could deal with this problem?!

What is your K? With N = 140, K = 4 requires about 116 Mb, and K = 5 requires
over 3 Gb. K = 10 requires about 4 petabytes (that's the unit above terabytes).

Walter Roberson <roberson@hushmail.com> wrote in message <hn6qam$sv7$1@canopus.cc.umanitoba.ca>...
> Frank Sabouri wrote:
> > Hello -
> >
> > I have problem of memory when I run: NK=nchoosek (1:N,K), in which N is
> > >40. I need to generate a "NK", wherein "N" is 140. Does anyone know
> > how I could deal with this problem?!
>
> What is your K? With N = 140, K = 4 requires about 116 Mb, and K = 5 requires
> over 3 Gb. K = 10 requires about 4 petabytes (that's the unit above terabytes).

I'm sure only Paris Hilton has a petabyte :| !

Oleg

Frank Sabouri wrote:

> Let me ask my question in other way: I have a matrix of data (140X15), I
> want to randomly generate as much as possible sub-matrices (6X15). It
> was why I used "nchoosek" to randomly set the sub-matices. There is any
> function that allow me to creat these submatices.

That would be 9381724380 combinations, each of which would occupy
6 * 15 * 8 = 720 bytes (unless you can use a datatype smaller than double
precision). The total would be 6291 gigabytes.

However, if you want "as many as possible", then you don't want to -randomly-
select subsets, you want to do all of them in sequence, since you are going to
eventually cover all of them. If your program is such that you can process one
of the submatrices and then throw that submatrix away, then you can use an
algorithm that iterative gives you the "next" submatrix each time, and you
would only need the 720 bytes plus the bytes you need to hold your
intermediate results plus some overhead bytes to store the state of the
iterator. I calculate that that would bring the calculation into the realm of
feasibility -- though it might take a few hours, depending on how much
manipulation of the matrix you need to do.

"Frank Sabouri" <Frank.Sabouri@gmail.com> wrote in message <hn6pst$d24$1@fred.mathworks.com>...
> Hello -
>
> Let me ask my question in other way: I have a matrix of data (140X15), I want to randomly generate as much as possible sub-matrices (6X15). It was why I used "nchoosek" to randomly set the sub-matices. There is any function that allow me to creat these submatices.
>
> Frank

  If what you mean is that you want to randomly select a single set of 6 rows out of 140 rows of a matrix as a submatrix, then what you need is 'randperm', not 'nchoosek'. The latter would give you all possible such choices, which is an awful lot of choices, namely 9,381,724,380 of them.

  For a single submatrix:

 p = randperm(140);
 submatrix = matrix(p(1:6),:);

(If you need many such submatrices, repeat the above. If you are worried about the very remote chance of repetitions, test for and reject them.)

Roger Stafford

Thanks Roger...Frank
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hn6sq5$g3s$1@fred.mathworks.com>...
> "Frank Sabouri" <Frank.Sabouri@gmail.com> wrote in message <hn6pst$d24$1@fred.mathworks.com>...
> > Hello -
> >
> > Let me ask my question in other way: I have a matrix of data (140X15), I want to randomly generate as much as possible sub-matrices (6X15). It was why I used "nchoosek" to randomly set the sub-matices. There is any function that allow me to creat these submatices.
> >
> > Frank
>
> If what you mean is that you want to randomly select a single set of 6 rows out of 140 rows of a matrix as a submatrix, then what you need is 'randperm', not 'nchoosek'. The latter would give you all possible such choices, which is an awful lot of choices, namely 9,381,724,380 of them.
>
> For a single submatrix:
>
> p = randperm(140);
> submatrix = matrix(p(1:6),:);
>
> (If you need many such submatrices, repeat the above. If you are worried about the very remote chance of repetitions, test for and reject them.)
>
> Roger Stafford