Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
combination from possible numbers

Subject: combination from possible numbers

From: omegayen

Date: 10 Jun, 2011 19:51:05

Message: 1 of 9

Hi,

I am interested in generating all the possible combinations of a vector of size 25 consisting of only elements of 1, 2, and 3

for example one solution would be

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

anyone know of way to do this?

Subject: combination from possible numbers

From: Shawn Bonneau

Date: 10 Jun, 2011 20:07:40

Message: 2 of 9

There is a perms function which will in general do what you want, but it has
a couple of limitations. First, it should only be used for vectors of length
10 or less. Testing this myself, the function took 1.17 seconds for a 10
element vector, and 54 seconds for an 11 element vector.

Secondly, this will yield a ton of repeat values since you have so many 1's
in your vector, and I assume you don't care which 1 is where.

Therefore you should write your own script that will calculate it. Perms did
it recursively, but you can make a pretty simple for loop structure to do
what you need. Make one for loop for the indexOf2 and a nested loop for the
indexOf3. Have them both go from 1:25. In the inner loop check if the two
indices are the same, since you don't want to have both the 2 and the 3 in
the same spot. If they are different, then create a new row in your
permutation list with ones everywhere, but 2 in the indexOf2 spot, and 3 in
the indexOf3 spot. You will also need a resultIndex variable to keep track
of which row you should be saving to.

"omegayen " <omegayen@ameritech.net> wrote in message
news:istsj9$m4q$1@newscl01ah.mathworks.com...
> Hi,
>
> I am interested in generating all the possible combinations of a vector of
> size 25 consisting of only elements of 1, 2, and 3
>
> for example one solution would be
> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
>
> anyone know of way to do this?

Subject: combination from possible numbers

From: Shawn Bonneau

Date: 10 Jun, 2011 20:14:51

Message: 3 of 9

By the way, the script I just made up to do this only took about 2 minutes
and 12 lines to make. It ran in 0.0132 seconds and only took 120 kb for the
answer to your 25 element (ignoring permutations of 1s) , as opposed to the
3512678 kb that were used by perms for an 11 element vector.

"Shawn Bonneau" <sbonneau@mathworks.com> wrote in message
news:isttic$oss$1@newscl01ah.mathworks.com...
> There is a perms function which will in general do what you want, but it
> has a couple of limitations. First, it should only be used for vectors of
> length 10 or less. Testing this myself, the function took 1.17 seconds for
> a 10 element vector, and 54 seconds for an 11 element vector.
>
> Secondly, this will yield a ton of repeat values since you have so many
> 1's in your vector, and I assume you don't care which 1 is where.
>
> Therefore you should write your own script that will calculate it. Perms
> did it recursively, but you can make a pretty simple for loop structure to
> do what you need. Make one for loop for the indexOf2 and a nested loop for
> the indexOf3. Have them both go from 1:25. In the inner loop check if the
> two indices are the same, since you don't want to have both the 2 and the
> 3 in the same spot. If they are different, then create a new row in your
> permutation list with ones everywhere, but 2 in the indexOf2 spot, and 3
> in the indexOf3 spot. You will also need a resultIndex variable to keep
> track of which row you should be saving to.
>
> "omegayen " <omegayen@ameritech.net> wrote in message
> news:istsj9$m4q$1@newscl01ah.mathworks.com...
>> Hi,
>>
>> I am interested in generating all the possible combinations of a vector
>> of size 25 consisting of only elements of 1, 2, and 3
>>
>> for example one solution would be
>> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
>>
>> anyone know of way to do this?
>

Subject: combination from possible numbers

From: dpb

Date: 10 Jun, 2011 20:16:55

Message: 4 of 9

omegayen wrote:

> Hi,
>
> I am interested in generating all the possible combinations of a vector
> of size 25 consisting of only elements of 1, 2, and 3
>
> for example one solution would be
> 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1 1 1 1 1 1 1 1 2 3
>
> anyone know of way to do this?

Is ones(1,25) also a solution?

Either way, I'm thinking the total memory required is large enough as to
prevent the likelihood of succeeding in the stated desired enumeration... :)

--

Subject: combination from possible numbers

From: Shawn Bonneau

Date: 10 Jun, 2011 20:18:38

Message: 5 of 9

It looks like I misread the problem. If you have varying numbers of 2s and
3s, you are right dpb. The number of potations would definitely be too great
of a memory demand.

"dpb" <non@non.net> wrote in message news:4DF27BB7.70806@non.net...
> omegayen wrote:
>
>> Hi,
>>
>> I am interested in generating all the possible combinations of a vector
>> of size 25 consisting of only elements of 1, 2, and 3
>>
>> for example one solution would be 1 1 1 1 1 1 1 1
>> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
>> 2 3
>>
>> anyone know of way to do this?
>
> Is ones(1,25) also a solution?
>
> Either way, I'm thinking the total memory required is large enough as to
> prevent the likelihood of succeeding in the stated desired enumeration...
> :)
>
> --
>

Subject: combination from possible numbers

From: dpb

Date: 10 Jun, 2011 21:01:14

Message: 6 of 9

Shawn Bonneau wrote:

> It looks like I misread the problem. If you have varying numbers of 2s
> and 3s, you are right dpb. The number of potations would definitely be
> too great of a memory demand.
...


I don't know; I wasn't sure what the problem statement is, either.

If taken at literal statement it's very, very large number...

--

Subject: combination from possible numbers

From: ImageAnalyst

Date: 10 Jun, 2011 21:21:27

Message: 7 of 9

If there are 3 possible states (1, 2, or 3) and 25 slots, then there
are 3^25 or 847 billion possible combinations. This isn't necessarily
a memory problem - it only is if he wants to store them all, but he
didn't say that. If you had a loop and just got one combination at a
time it would use practically no memory although I get it would take a
long time to loop through 847 giga-combinations, even with a 3
Gigahertz CPU. Though I have heard of some computations taking hours
or maybe days to finish so it's not unheard of.

I'm really wondering why this is needed in the first place. Is this a
real world problem, or some some hypothetical thought experiment?
What is the actual grand scheme of things where this one task is
needed? There could be a better, alternate way that is more efficient.

Subject: combination from possible numbers

From: Steven_Lord

Date: 13 Jun, 2011 03:13:01

Message: 8 of 9



"ImageAnalyst" <imageanalyst@mailinator.com> wrote in message
news:a572b068-33fb-45df-8872-2c15d09bf6df@m10g2000yqd.googlegroups.com...
> If there are 3 possible states (1, 2, or 3) and 25 slots, then there
> are 3^25 or 847 billion possible combinations. This isn't necessarily
> a memory problem - it only is if he wants to store them all, but he
> didn't say that. If you had a loop and just got one combination at a
> time it would use practically no memory although I get it would take a
> long time to loop through 847 giga-combinations, even with a 3
> Gigahertz CPU. Though I have heard of some computations taking hours
> or maybe days to finish so it's not unheard of.

3^25 seconds is about 26,750 years. Even if you processed 10,000
combinations per second, you're still talking over 2 and a half years.

http://www.google.com/#hl=en&q=3^25+seconds+in+years

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

Subject: combination from possible numbers

From: omegayen

Date: 13 Jun, 2011 18:05:14

Message: 9 of 9

"Steven_Lord" <slord@mathworks.com> wrote in message <it3v7u$lo$1@newscl01ah.mathworks.com>...
>
>
> "ImageAnalyst" <imageanalyst@mailinator.com> wrote in message
> news:a572b068-33fb-45df-8872-2c15d09bf6df@m10g2000yqd.googlegroups.com...
> > If there are 3 possible states (1, 2, or 3) and 25 slots, then there
> > are 3^25 or 847 billion possible combinations. This isn't necessarily
> > a memory problem - it only is if he wants to store them all, but he
> > didn't say that. If you had a loop and just got one combination at a
> > time it would use practically no memory although I get it would take a
> > long time to loop through 847 giga-combinations, even with a 3
> > Gigahertz CPU. Though I have heard of some computations taking hours
> > or maybe days to finish so it's not unheard of.
>
> 3^25 seconds is about 26,750 years. Even if you processed 10,000
> combinations per second, you're still talking over 2 and a half years.
>
> http://www.google.com/#hl=en&q=3^25+seconds+in+years
>
> --
> Steve Lord
> slord@mathworks.com
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com


alright thanks for the insights guys.. yeah it was more of a hypothetical thought experiment but has application to a real world type of problem, but yeah given today's technology it would just take way too long to be feasible thanks.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us