Seeking algorithm to compute number of possibilities...
MLH
the number of possible combinations
is equal to 2^3.
But if I have 3 things, 2 of which can
be in 2 states and the other in 3 states,
what's the simplest expression that will
accurately compute the permutationjs
possible?
ManningFan
might not make sense but the best formula to compute that would be 2X +
3Y, where X = 2 and Y = 1. X + Y = the number of things you're talking
about.
Thelma Roslyn Lubkin
: That's a bad example because it uses the same number twice, so this
: might not make sense but the best formula to compute that would be 2X +
: 3Y, where X = 2 and Y = 1. X + Y = the number of things you're talking
: about.
Are you assuming 2 'things' capable of being in 2 states
simultaneously? I assumed that MLH meant
But if I have 3 things, 2 of which can
be in *1 of* 2 states and the other
in *1 of* 3 states:
2*2*3 ot #possPos1 * #possPos2 * #possPos1 3
My other, less favored, interpretation would be that
things 1 and 2 form a joint thing that can be in 2
states, e.g. state 1: thing 1=red, thing 2=blue
state 2: thing 1=white, thing 2=brown
2*3 or #possjointPos1,2 * #possPos3
for poss[ibilities] and Pos[itions]
--thelma
:>
Rick Brandt
(2^2)*3
--
Rick Brandt, Microsoft Access MVP
Email (as appropriate) to...
RBrandt at Hunter dot com
MLH
Rick, your answer looks the simplest. To
be sure, though, I'll add clarity to the Q
for Manning's and Thelma's benefit...
You walk into a room which has nothing
in it but some water, a lite bulb and a radio.
If the water can be in 3-states: solid, liquid or gas &
If the lite can be on or off &
if the radio can be on or off
How many conditions (each condition being
a single unique combination of states of the
above 3 objects) are possible?
According to Rick, 12 ==> 2 to the 2nd power,
all that times 3. I agree. A brute force approach
to the question proves his answer correct, I think.
Even though, as an answer, it is correct - its not
the algorithm I was seeking. However, to Rick's
credit, an algorithm can be inferred I think. Perhaps
its this:
If you have a collection of any number of things
that can be in any one of any number of states,
they can be grouped so that all things that can be
in the same number of states together. Call these
groups 'factors'. Make a exponential calculation
in each group, raising the number of states (base)
to the power of the number of things (exponent).
Then multiply the factors. The answer equals the
permutations.
In the water, lite bulb, radio example; there are two
things that can be in two states (radio & lite bulb)
and one thing that can be in two states (water). So
the radio & lite bulb are grouped together in the
group of things that can be in 2-states. The water
is in a group by itself that can be in 3-states. Now
the factors:
First group: 2 states raised to the power of 2 things = 4
Sec group: 3 states raised to the power of 1 thing = 3
Multiplying your factors, 3 x 4 gives you 12.
Sound about rght, Rick? Anyone else agree? Disagree?
Rick, if that's right, and I apply the algorithm to the following
dilemma: I have 8 marbles that can be red, blue or green,
2 frogs that can be jumping or not, 3 people that can be
eating, sleeping or scuba diving and 4-outlaws that can
be dead or alive. All these things are out on the beach at
a swell dive spot. The number of possible combinations
of all these things (permutations) is 177183. Is that what
you would come up with, Rick? Note: I'm not certain of
this answer. Reverse engineering your answer to imply an
algorithm and using it is all I did here.
MLH
I meant to post was 6,377,292 ==> not 177,183.
Rick Brandt
news:1n38o29hrsm6ubm02...@4ax.com...
Don't over think this. Possible combinations are derived by multiplying the
possible states of each entity by the possible states of the others. Raising to
a power is merely shorthand for the multiplying and is only possible any time
the number of possible states between entities is the same. It is not when the
possible number of states is different.
A die has 6 possible states so 2 dice have 6^2 outcomes and 3 dice have 6^3, but
only when all die have the same number of sides. If I have one die with 6 sides
and one with 5 then there are 5*6 possible outcomes.
MLH
<rickb...@hotmail.com> wrote:
>Don't over think this. Possible combinations are derived by multiplying the
>possible states of each entity by the possible states of the others. Raising to
>a power is merely shorthand for the multiplying and is only possible any time
>the number of possible states between entities is the same.
Gotcha. So, applying the above to the question regarding the marbles,
frogs, people and outlaws, whats the number of combinations you come
up with?
Thelma Roslyn Lubkin
: On Sat, 16 Dec 2006 16:14:08 GMT, "Rick Brandt"
: <rickb...@hotmail.com> wrote:
Using basic I got that
3^8 * 2^2 * 3^3 * 2^4 = 11337408
marbles frogs people outlaws
I think that your algorithm with its shortcut is fine. In aircode
[even worse than aircode I'm afraid] form:
if N=number of EntityTypes()= array of number of Entities of each Type,
EntityStates()= array of number of States for each EntityType
Combinations = 1
for Type = 1 to N
Combinations = Combinations *
EntityStates(Type)^EntityTypes(Type)
--thelma
MLH
I haven't a clue who's right. I'm not sure what algorithm Rick was
using. Thx for the input.
Thelma Roslyn Lubkin
: So we got two different answers. That's what I was afraid of.
: I haven't a clue who's right. I'm not sure what algorithm Rick was
: using. Thx for the input.
We get 2 different answers, but from reading your description
of what you did, it seems that we're using the same algorithm.
So it seems to come down to arithmetic...
--thelma
Rick Brandt
> So we got two different answers. That's what I was afraid of.
> I haven't a clue who's right. I'm not sure what algorithm Rick was
> using. Thx for the input.
8 marbles that can be red, blue or green,
2 frogs that can be jumping or not, 3 people that can be
eating, sleeping or scuba diving and 4-outlaws that can
be dead or alive.
Not
(3^8)*(2^2)*(3^3)*(4^2)
6561*4*27*16 = 11,337,408
I seem to agree with Thelma. How did you get your answer?
It's not really a great example and maybe that's why we don't get the same
answer as you do. A rolled die can come up with one of 6 different sides on
top. A solid colored marble is ALWAYS one color. It has no possibility of
being three possible colors as in your example. Did you mean that of the 8
marbles some of them will be this, that, or the other color? That would
represent a completely different problem.
It would be more realistic and less confusing to just consider these as 8 table
fields each if which can have one of three possible entries, 6 fields that each
have two possible entries, and 3 fields that each have 3 possible entries.
(3^8) * (2^6) * (3^3)
6561 * 64 * 37 = 15536448
Rick Brandt
news:Ej0hh.25920$9v5....@newssvr29.news.prodigy.net...
Fat-fingered that one. Last line should be
6561 * 64 * 27 = 11,337,408
Thelma Roslyn Lubkin
: It would be more realistic and less confusing to just consider these
: as 8 table
: fields each if which can have one of three possible entries, 6
: fields that each
: have two possible entries, and 3 fields that each have 3 possible entries.
: (3^8) * (2^6) * (3^3)
: 6561 * 64 * 37 = 15536448
I disagree. That way of doing it requires you to pre-scan the
number of possibilities [states] for each entity type,
combine entity types that have the same number of possibilities,
and only then compute the number of permutations. You also lose
the clarity of seeing immediately the number of possibilities
associated with each entity type.
--thelma
: --
Rick Brandt
"Thelma Roslyn Lubkin" <the...@alpha2.csd.uwm.edu> wrote in message
news:em25vq$u9i$1...@uwm.edu...
> Rick Brandt <rickb...@hotmail.com> wrote:
>
> : It would be more realistic and less confusing to just consider these
> : as 8 table
> : fields each if which can have one of three possible entries, 6
> : fields that each
> : have two possible entries, and 3 fields that each have 3 possible entries.
>
> : (3^8) * (2^6) * (3^3)
> : 6561 * 64 * 37 = 15536448
>
> I disagree. That way of doing it requires you to pre-scan the
> number of possibilities [states] for each entity type,
> combine entity types that have the same number of possibilities,
> and only then compute the number of permutations. You also lose
> the clarity of seeing immediately the number of possibilities
> associated with each entity type.
I simply meant that thinking about the problem as fields with possible entries
was easier than thinking about colored marbles and jumping frogs.
CDMAP...@fortunejames.com
4 calling birds that can be eating, soaring or doing nothing
3 french hens French or not
2 turtle doves that are posting to CDMA or not
(1 + e + s) ^ 4 * (1 + f) ^ 3 * (1 + p) ^ 2
Total possibilities = 3^4 * 2^3 * 2^2
How can I list all the possibilities? By multiplying out the
polynomial.
If the birds can be individually distinguished:
(1 + e1 + s1) (1 + e2 + s2) (1 + e3 + s3) (1 + e4 + s4) (1 + f1) (1 +
f2) (1 + f3) (1 + p1) (1 + p2)
Is it possible to determine the coefficient of a specific term without
multiplying out the polynomial? Yes
E.g.,
Suppose we only have the two indistinguishable turtle doves.
(1 + p) ^ 2
Realize that, in general, the polynomial might have been something like
(1 + p + p^2 + p^3) ^ 43 so the following is used:
It's necessary to put the polynomial into a more useful form. In
general, 1 + r + r^2 + ... + r^n = 1 - r^(n+1) / (1 - r).
(1 + p) ^ 2 = [(1 - p^2) / (1 - p)] ^ 2
Note that 1 / (1 - x) = 1 + x + x^2 + ...
By differentiating the terms of 1 / (1 - x) and using a dummy variable,
along with some clean-up,
1 / (1 - x) ^ (r + 1) = Summation from k = 0 to infinity of C(k + r, r)
x ^ k where C(m, n) = m! / n!(m - n)!
This is from page 505 of Discrete Mathematics by Jerrold Grossman, ISBN
0-02-348331-8, 1990 Macmillan, Inc.
Note that multiplying by x ^ c just shifts the exponent of x by m.
I.e.,
x ^ c / (1 - x) ^ (r + 1) = Summation from k = 0 to infinity of C(k +
r, r) x ^ (k + c)
So now a way exists to determine the overall contribution a given
variable makes to a specific term.
What is the coefficient of p^1?
(1 - p ^ 2) ^ 2 / (1 - p) ^ 2 contributes 2 to the coefficient of p
I.e., C(1 + 1,1) = 2!/ 1!1! = 2, -2 * C(-1 + 1, 1) = 0 and C(-3 + 1,
1) = 0. Use 0 whenever you get a negative number factorial since that
indicates that the exponents of the p polynomial are already too large
to contribute to p.
Thus the first turtle dove can be posting to CDMA with the second
turtle dove not posting (perhaps they share the same computer) or the
first turtle dove is not posting to CDMA with the second turtle dove
posting to CDMA. Of course, since you can't tell the turtle doves
apart anyway you can only note that a single turtle dove is posting to
CDMA. If you want to cross states and ask how many combinations have a
total of 4 calling birds, french hens and turtle doves flying, that's a
different kettle of fish, but it's not hard to see how to get those
polynomials either.
This should give you the information you need to build your algorithm.
Note that this answer might contain more detailed than your original
request implied.
James A. Fortune
CDMAP...@FortuneJames.com
Disclaimer: With few exceptions, I don't claim to know much about
anything unless I've written a computer program to do it.
David F Cox
If the first marble we pick up is red then it is a different marble than we
picked up when the the first marble was blue.
If the first frog we pick up was jumping it can be the same frog that we
picked up when it was sleeping.
two marbles two colors results in the possibilities:
RR RB BB
2 frogs jumping or sleeping:
F1J & F2J
F1J & F2S
F1S & F2S
F1S & F2J
"Rick Brandt" <rickb...@hotmail.com> wrote in message
news:dZ0hh.25931$9v5....@newssvr29.news.prodigy.net...
MLH
<rickb...@hotmail.com> wrote:
>I seem to agree with Thelma. How did you get your answer?
Believe me, I'm not confident uf my answer - not even my arithmetic.
Only with small numbers I can do on a sheet of paper do I feel some
sort of confidence. Here's where I was coming from...
3-States 2-States
------------- ---------------
8 marbles 2 frogs
3 people 4 outloaws
11 things 6 things
(3^11) x (2^6) = 11,337,408
Last time I used (3^11) x (6^2) mistakenly => which = 6,377,292
I didn't differentiate between people & marbles. My thinking was
both were just things that could be in 1 of 2 states. Same went
for frogs & outlaws.
I could have worded my question ==> How many combinations
are possible with 11 things (2-states) and 6 things (3-states). I'm
probably way off on this.
MLH
difficulty getting your point with the 2 frogs jumping
or sleeping illustration. I belive yields 4 (2^2). That's
what you have shown. If that's the point, I think we
are all in agreement with it. Rick pointed out a few
posts up that the exponential expression was a
shorthand notation used for calculating possible
combinations in a things - states scenario.
On Sun, 17 Dec 2006 04:29:08 GMT, "David F Cox" <nos...@nospam.zz>
wrote:
MLH
looks good to me (now that I realized my arithmetic was slightly
bent).
Many thx, Thelma.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
MLH
Anyone else have a take on this?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
MLH
them into (3^4) x (2^5). First time around,
I did (3^4) x (5^2) which was goofy.
David F Cox
confusion in the examples given between cases where order matters
(combinations) and does not matter (permutations). Different formulae apply.
In this field the slightest imprecision in thought can result in the answer
being billions out.
http://en.wikipedia.org/wiki/Combinatorics
http://www.algebra.com/algebra/homework/Permutations/Combinatorics.wikipedia
http://www.stat.berkeley.edu/users/stark/SticiGui/Text/ch7.htm
"MLH" <CR...@NorthState.net> wrote in message
news:6efao25vhhilgeda4...@4ax.com...