Thread Subject:

How to reduce the combinations' dimension--speed up my cross product

I need to calculate the product of 3 elements which are randomly selected from a vector with size 2000*1, so that I will have 2000*1999*19987/3 different combinations. This process time takes me tremendous time........

Now I am currently using a code, (> n = size(b,1);
> aa = zeros(1,n*(n-1)*(n-2)/6);
> c1 = 0;
> for k = 2:n-1
> c2 = c1+(k-1)*(n-k);
> aa(c1+1:c2) = b(1:k-1)*b(k)*b(k+1:n).';
> c1 = c2;
> end
>
> )Thanks to Roger Stafford


Is there a way to speed up the running process?

I am also thinking to extract 1000 products which represent the most information from the set of all products (2000*1999*19987/3)?
Is there an efficient way to do that?

Thanks a lot in advance

"Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message
news:ivevlp$kdi$1@newscl01ah.mathworks.com...
>
>
>
> I need to calculate the product of 3 elements which are randomly selected
> from a vector with size 2000*1, so that I will have 2000*1999*19987/3
> different combinations. This process time takes me tremendous
> time........

If you were to compute one of these combinations each second, you'd be done
after only:

>> numCombinations = nchoosek(2000, 3);
>> minutes = (numCombinations/60);
>> hours = minutes/60;
>> days = hours/24;
>> years = days/365
years =
          42.2163242009132

a tad over 42 years. [You'd be able to compute more than one combination per
second, but you're still talking about spending MONTHS or perhaps YEARS
computing.] Storing all the combinations as a big double array would
require:

>> bytes = 8*(numCombinations*3);
>> kb = bytes/1024;
>> mb = kb/1024;
>> gb = mb/1024

gb =

           29.757633805275

close to 30 GB of contiguous memory.

Rethink your approach. Why are you trying to do this -- what's your goal?
Perhaps (likely) there's a way to do what you want without creating a huge
array and taking a very long time to perform the computations.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Hi Steven

Thanks a lot for your quick and kindly reply.

You are correct, it will take toooooo much time to compute, that's why I am think to extract the combinations, or only compute a subset of combinations. The subset may include only 1000 combinations from 2000*1999*19987/3 products.


eg

m =

     6 7 8 1 2 3 4 5

if I select 3 elements there will be 56 combinations. However, I only want to obtain the 10/56 combinations, where the 10 products should be the most representative ones. How should I do this?

"Steven_Lord" <slord@mathworks.com> wrote in message <ivf2lq$sq$1@newscl01ah.mathworks.com>...
>
>
> "Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message
> news:ivevlp$kdi$1@newscl01ah.mathworks.com...
> >
> >
> >
> > I need to calculate the product of 3 elements which are randomly selected
> > from a vector with size 2000*1, so that I will have 2000*1999*19987/3
> > different combinations. This process time takes me tremendous
> > time........
>
> If you were to compute one of these combinations each second, you'd be done
> after only:
>
> >> numCombinations = nchoosek(2000, 3);
> >> minutes = (numCombinations/60);
> >> hours = minutes/60;
> >> days = hours/24;
> >> years = days/365
> years =
> 42.2163242009132
>
> a tad over 42 years. [You'd be able to compute more than one combination per
> second, but you're still talking about spending MONTHS or perhaps YEARS
> computing.] Storing all the combinations as a big double array would
> require:
>
> >> bytes = 8*(numCombinations*3);
> >> kb = bytes/1024;
> >> mb = kb/1024;
> >> gb = mb/1024
>
> gb =
>
> 29.757633805275
>
> close to 30 GB of contiguous memory.
>
> Rethink your approach. Why are you trying to do this -- what's your goal?
> Perhaps (likely) there's a way to do what you want without creating a huge
> array and taking a very long time to perform the computations.
>
> --
> Steve Lord
> slord@mathworks.com
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

"Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message <ivf45m$5qf$1@newscl01ah.mathworks.com>...
> Hi Steven
>
> Thanks a lot for your quick and kindly reply.
>
> You are correct, it will take toooooo much time to compute, that's why I am think to extract the combinations, or only compute a subset of combinations. The subset may include only 1000 combinations from 2000*1999*19987/3 products.
>
>
> eg
>
> m =
>
> 6 7 8 1 2 3 4 5
>
> if I select 3 elements there will be 56 combinations. However, I only want to obtain the 10/56 combinations, where the 10 products should be the most representative ones. How should I do this?
>
> "Steven_Lord" <slord@mathworks.com> wrote in message <ivf2lq$sq$1@newscl01ah.mathworks.com>...
> >
> >
> > "Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message
> > news:ivevlp$kdi$1@newscl01ah.mathworks.com...
> > >
> > >
> > >
> > > I need to calculate the product of 3 elements which are randomly selected
> > > from a vector with size 2000*1, so that I will have 2000*1999*19987/3
> > > different combinations. This process time takes me tremendous
> > > time........
> >
> > If you were to compute one of these combinations each second, you'd be done
> > after only:
> >
> > >> numCombinations = nchoosek(2000, 3);
> > >> minutes = (numCombinations/60);
> > >> hours = minutes/60;
> > >> days = hours/24;
> > >> years = days/365
> > years =
> > 42.2163242009132
> >
> > a tad over 42 years. [You'd be able to compute more than one combination per
> > second, but you're still talking about spending MONTHS or perhaps YEARS
> > computing.] Storing all the combinations as a big double array would
> > require:
> >
> > >> bytes = 8*(numCombinations*3);
> > >> kb = bytes/1024;
> > >> mb = kb/1024;
> > >> gb = mb/1024
> >
> > gb =
> >
> > 29.757633805275
> >
> > close to 30 GB of contiguous memory.
> >
> > Rethink your approach. Why are you trying to do this -- what's your goal?
> > Perhaps (likely) there's a way to do what you want without creating a huge
> > array and taking a very long time to perform the computations.
> >
> > --
> > Steve Lord
> > slord@mathworks.com
> > To contact Technical Support use the Contact Us link on
> > http://www.mathworks.com
- - - - - - - -
  The best way to select random combinations of three distinct elements is to select random permutations of three distinct elements and that can be done using 'randperm'. For every combination of three there are six permutations of it, so the statistics would be equivalent.

 p = randperm(length(m));
 q = sort(p(1:3));
 s = m(q); % s is a randomly selected combination of three elements in m

  Repeat that in an appropriate for-loop the desired number of times. If you are worried about selecting the same combination twice, the odds of that ever happening for a thousand combinations out of a total of 2000*1999*1998/6 are about 1 in 2,666. Perhaps you could afford to neglect that possibility.

Roger Stafford

Hi Roger,

Thanks a lot for your kind help.

So I will use this randperm to generate my index sequence and then according to this index I need to calculate the product of any three values.

Is there a clever way to address this issue?
BIG thanks

"Roger Stafford" wrote in message <ivfh09$gkk$1@newscl01ah.mathworks.com>...
> "Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message <ivf45m$5qf$1@newscl01ah.mathworks.com>...
> > Hi Steven
> >
> > Thanks a lot for your quick and kindly reply.
> >
> > You are correct, it will take toooooo much time to compute, that's why I am think to extract the combinations, or only compute a subset of combinations. The subset may include only 1000 combinations from 2000*1999*19987/3 products.
> >
> >
> > eg
> >
> > m =
> >
> > 6 7 8 1 2 3 4 5
> >
> > if I select 3 elements there will be 56 combinations. However, I only want to obtain the 10/56 combinations, where the 10 products should be the most representative ones. How should I do this?


> The best way to select random combinations of three distinct elements is to select random permutations of three distinct elements and that can be done using 'randperm'. For every combination of three there are six permutations of it, so the statistics would be equivalent.
>
> p = randperm(length(m));
> q = sort(p(1:3));
> s = m(q); % s is a randomly selected combination of three elements in m
>
> Repeat that in an appropriate for-loop the desired number of times. If you are worried about selecting the same combination twice, the odds of that ever happening for a thousand combinations out of a total of 2000*1999*1998/6 are about 1 in 2,666. Perhaps you could afford to neglect that possibility.
>
> Roger Stafford

"Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message <ivgrqs$6om$1@newscl01ah.mathworks.com>...
> Hi Roger,
>
> Thanks a lot for your kind help.
>
> So I will use this randperm to generate my index sequence and then according to this index I need to calculate the product of any three values.
>
> Is there a clever way to address this issue?
> BIG thanks

I strongly recommend to take a look a SHUFFLE by Jan Simon:
http://www.mathworks.com/matlabcentral/fileexchange/27076-shuffle

It's very efficient when the drawing population length (3) is much smaller than the total population (n):

b=rand(1,2000);
n = length(b);
m = 1000;
a = zeros(1,m);
for k=1:m
    a(k) = prod(b(Shuffle(n,'index',3)));
end

% Bruno

Thanks a lot Bruno. This really helps!
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ivgt45$9jv$1@newscl01ah.mathworks.com>...
> "Skirt Zhang" <silence_qunzi@hotmail.com> wrote in message <ivgrqs$6om$1@newscl01ah.mathworks.com>...
> > Hi Roger,
> >
> > Thanks a lot for your kind help.
> >
> > So I will use this randperm to generate my index sequence and then according to this index I need to calculate the product of any three values.
> >
> > Is there a clever way to address this issue?
> > BIG thanks
>
> I strongly recommend to take a look a SHUFFLE by Jan Simon:
> http://www.mathworks.com/matlabcentral/fileexchange/27076-shuffle
>
> It's very efficient when the drawing population length (3) is much smaller than the total population (n):
>
> b=rand(1,2000);
> n = length(b);
> m = 1000;
> a = zeros(1,m);
> for k=1:m
> a(k) = prod(b(Shuffle(n,'index',3)));
> end
>
> % Bruno