How can I use the ( nchoosek ) for this case nchoosek(x,y) where x=[1:1:80] , and y=64;

3 views (last 30 days)
I have the following
x=[1:1:26]
y=16;
C = nchoosek(x,y)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
and I need to find the same process for
x=[1:1:80]
y=64;
C = nchoosek(x,y)
I get the following warrning message
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only
accurate to 15 digits.
How can i find C ???
  1 Comment
Dyuman Joshi
Dyuman Joshi on 20 Jul 2022
Edited: Dyuman Joshi on 20 Jul 2022
From the documentation of nchoosek -
> "C = nchoosek(v,k) is only practical for situations where length(v) is less than about 15."
The lenght of your vector is 80. So nchoosek won't work as you want it to work.
You can find out nchoosek(80,64) but computing nchoosek(1:80,64) is going to be extremely difficult. (The difficult is pointed out by @Jan below)

Sign in to comment.

Answers (3)

Jan
Jan on 20 Jul 2022
Edited: Jan on 20 Jul 2022
80 over 64 is 26'958'221'130'508'525. Then nchoosek(1:80, 64) needs 26958221130508525 * 64 * 8 Bytes in the RAM, which is 1,38 PetaByte, which 1'380'000 GigaByte.
There is no computer on earth, which has this amout of RAM.
You can determine the value of 80 over 64 accurately by:
nchoosek(vpa(80), vpa(64))
ans = 
26958221130508525.0
Creating nchoosek(1:26, 16) takes 0.5 seconds in my Matlab 2018b and replies a matrix using 1.1GB. If this could be extrapolated, producing nchoosek(1:80, 64) would take about 8 day to be computed.
  1 Comment
Steven Lord
Steven Lord on 20 Jul 2022
Leaving aside the question of generating and storing the data, there's the question of what you're planning to do with this.
c = nchoosek(int64(80), 64)
c = int64 26958221130508525
Processing one entry in that list every second would take you:
format longg
y = years(seconds(c))
y =
854272020.013483
over 850 million years. Process at a thousand entries a second and the time is cut down to "only' 850 thousand years.
If you tell us how you were hoping to use the data we may be able to offer a more memory and time efficient approach to solve that problem.

Sign in to comment.


Jon
Jon on 20 Jul 2022
Using
b = nchoosek(80,64)
You will see that there are approximately 2.6958 E16 ways of choosing 64 elements out of your vector of 80 values.
The result of
C = nchoosek(1:80,64)
would most likely exceed the size of your available memory
I suggest that you further evaluate what you are actually trying to achieve. What would you do with all of those choices?
  1 Comment
Jon
Jon on 20 Jul 2022
Took me awhile to push the submit button, I see that by the time I did @Jan has also told you about the size and time issues with this computation

Sign in to comment.


John D'Errico
John D'Errico on 20 Jul 2022
As Jan pointed out, you CANNOT solve your problem in this way. Using nchoosek in this form, it almost always is a form of brute force. Evaluate EVERY possible solution, then pick the one that is best.
And the problem is, you can't do it. The search space is simply too large. We get spoiled, with big fast computers on our laps or desks, thinking they can do anything, solve every possible problem. They can't. And you cannot afford a big enough comouter, because as soon as you do, your problem will expand to nchoosek(1:100) or 200, etc.
A basic rule of computing that I posed many years ago is that problems ALWAYS expand to be as large as the computer you have at your fingertips, and then just a bit larger. After all, why solve small problems? Someone else already did them, and those problems were easy.
The thing is, this means you need to use creativity. Think outside the box. Mathematics is the means of avoiding those brute force problems. Convert your large problem into something that can be solved using existing tools and methods.
One idea may be to convert your problem into a search, perhaps some sort of search routine that uses a genetic algorithm to find the solution, but something that will not need to evaluate every possible solution in the search space.
Or you may be abe to use other techniques, other ways to view the problem. Can you simplify it in some way, find an approximation that will reduce the computational load.
Of course, these are just general thoughts, that reflect on the fact you CANNOT solve the problem using brute force, so it leaves you little choice if you want to find a solution.

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!